結果

問題 No.235 めぐるはめぐる (5)
ユーザー ei1333333ei1333333
提出日時 2015-08-29 20:10:48
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,052 ms / 10,000 ms
コード長 5,647 bytes
コンパイル時間 2,548 ms
コンパイル使用メモリ 189,144 KB
実行使用メモリ 55,332 KB
最終ジャッジ日時 2023-09-25 19:45:05
合計ジャッジ時間 6,784 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,052 ms
42,680 KB
testcase_01 AC 485 ms
55,332 KB
testcase_02 AC 670 ms
43,412 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
const int MOD = 1000000007;

struct SegmentTree
{
  struct node {
    int sum, lazy;
    node():sum(0), lazy(0){};
  };
  vector< node > seg;
  vector< int > Csum;
  int sz;

  SegmentTree(int n, vector< int >& C)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(sz * 2, node());
    Csum.resize(sz + 1, 0);
    for(int i = 0; i < n; i++) {
      Csum[i + 1] = C[i];
    }
    for(int i = 1; i < Csum.size(); i++) {
      (Csum[i] += Csum[i - 1]) %= MOD;
    }
  }

  void Set(int k, int x)
  {
    seg[k + sz - 1].sum += x;
  }
  void Build()
  {
    for(int k = sz - 2; k >= 0; k--) {
      seg[k].sum = (seg[2 * k + 1].sum + seg[2 * k + 2].sum) % MOD;
    }
  }

  int Sum(int l, int r)
  {
    return((Csum[r] - Csum[l] + MOD) % MOD);
  }

  void Update(int k, int l, int r)
  {
    (seg[k].sum = seg[2 * k + 1].sum + seg[2 * k + 2].sum) %= MOD;
    (seg[k].sum += (int64)Sum(l, (l + r) >> 1) * seg[2 * k + 1].lazy % MOD) %= MOD;
    (seg[k].sum += (int64)Sum((l + r) >> 1, r) * seg[2 * k + 2].lazy % MOD) %= MOD;
  }

  void Evaluation(int k, int l, int r)
  {
    if(seg[k].lazy == 0) return;
    if(k < sz - 1) {
      (seg[2 * k + 1].lazy += seg[k].lazy) %= MOD;
      (seg[2 * k + 2].lazy += seg[k].lazy) %= MOD;
      seg[k].lazy = 0;
      Update(k, l, r);
    } else {
      (seg[k].sum += (int64)Sum(l, r) * seg[k].lazy % MOD) %= MOD;
      seg[k].lazy = 0;
    }
  }

  void Add(int a, int b, int k, int z, int l, int r)
  {
    Evaluation(k, l, r);
    if(a >= r || b <= l) return;
    if(a <= l && r <= b) {
      (seg[k].lazy += z) %= MOD;
      Evaluation(k, l, r);
    } else {
      Add(a, b, 2 * k + 1, z, l, (l + r) >> 1);
      Add(a, b, 2 * k + 2, z, (l + r) >> 1, r);
      Update(k, l, r);
    }
  }
  void Add(int a, int b, int z)
  {
    Add(a, b, 0, z, 0, sz);
  }

  int RSQ(int a, int b, int k, int l, int r)
  {
    Evaluation(k, l, r);
    if(a >= r || b <= l) return(0);
    if(a <= l && r <= b) return(seg[k].sum);
    return((RSQ(a, b, 2 * k + 1, l, (l + r) >> 1) + RSQ(a, b, 2 * k + 2, (l + r) >> 1, r)) % MOD);
  }
  int RSQ(int a, int b)
  {
    return(RSQ(a, b, 0, 0, sz));
  }
};

struct node {
  int ParIdx, ParDepth, Deep, Size;
} pool[200000];

typedef vector< vector< int > > Graph;
Graph graph;
vector< int > sz, nowIdx, nowDepth;
vector< SegmentTree > segs;
int ptr;
vector< vector< int > > ns;


inline int SizeDfs(int idx, int prev)
{
  int ret = 0;
  for(int i = 0; i < graph[idx].size(); i++) {
    if(graph[idx][i] != prev) {
      ret += SizeDfs(graph[idx][i], idx);
    }
  }
  return(sz[idx] = ret);
}
  
inline void makeDfs(int idx, int prev, int treeIdx, int treeDepth, int Deep) {
  pool[treeIdx].Size++;
  nowIdx[idx] = treeIdx;
  nowDepth[idx] = treeDepth;
  ns[treeIdx].push_back(idx);

  pair< int, int > ret = make_pair(-1, -1);
  for(int i = 0; i < graph[idx].size(); i++) {
    if(graph[idx][i] != prev) {
      ret = max(ret, make_pair(sz[graph[idx][i]], i));
    }
  }
  
  for(int i = 0; i < graph[idx].size(); i++) {
    if(graph[idx][i] != prev) {
      if(ret.second == i) {
        makeDfs(graph[idx][i], idx, treeIdx, treeDepth + 1, Deep);
      } else {
        pool[ptr++] = (node){treeIdx, treeDepth, Deep + 1, 0};
        makeDfs(graph[idx][i], idx, ptr - 1, 0, Deep + 1);
      }
    }
  }
  
}
  
void CentroidPathDecomposition(const Graph& graph)
{
  sz.resize(graph.size());
  nowIdx.resize(graph.size());
  nowDepth.resize(graph.size());
  ns.resize(graph.size());
  
  SizeDfs(0, -1);
  ptr = 0;
  pool[ptr++] = (node){-1, -1, 0, 0};
  makeDfs(0, -1, 0, 0, 0);
}

void update(int A, int B, int Z)
{
  int idx1 = nowIdx[A], dep1 = nowDepth[A];
  int idx2 = nowIdx[B], dep2 = nowDepth[B];
  while(idx1 != idx2) {
    if(pool[idx1].Deep > pool[idx2].Deep) {
      segs[idx1].Add(0, dep1 + 1, Z);
      dep1 = pool[idx1].ParDepth;
      idx1 = pool[idx1].ParIdx;
    } else {
      segs[idx2].Add(0, dep2 + 1, Z);
      dep2 = pool[idx2].ParDepth;
      idx2 = pool[idx2].ParIdx;
    }
  }
  if(dep1 > dep2) swap(dep1, dep2);
  segs[idx1].Add(dep1, dep2 + 1, Z);
}

int dist(int A, int B)
{
  int idx1 = nowIdx[A], dep1 = nowDepth[A];
  int idx2 = nowIdx[B], dep2 = nowDepth[B];
  int ret = 0;
  while(idx1 != idx2) {
    if(pool[idx1].Deep > pool[idx2].Deep) {
      (ret += segs[idx1].RSQ(0, dep1 + 1)) %= MOD;
      dep1 = pool[idx1].ParDepth;
      idx1 = pool[idx1].ParIdx;
    } else {
      (ret += segs[idx2].RSQ(0, dep2 + 1)) %= MOD;
      dep2 = pool[idx2].ParDepth;
      idx2 = pool[idx2].ParIdx;
    }
  }
  if(dep1 > dep2) swap(dep1, dep2);
  (ret += segs[idx1].RSQ(dep1, dep2 + 1)) %= MOD;
  return(ret);
}


int N, S[200000], C[200000];
int Q;


int main()
{
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    scanf("%d", &S[i]);
  }
  for(int i = 0; i < N; i++) {
    scanf("%d", &C[i]);
  }
  graph.resize(N);
  for(int i = 0; i < N - 1; i++) {
    int A, B;
    scanf("%d %d", &A, &B);
    --A, --B;
    graph[A].push_back(B);
    graph[B].push_back(A);
  }
  CentroidPathDecomposition(graph);

  vector< int > ll(N);
  for(int i = 0; i < ptr; i++) {
    for(int j = 0; j < ns[i].size(); j++) {
      ll[j] = C[ns[i][j]];
    }
    segs.push_back(SegmentTree(ns[i].size(), ll));
    for(int j = 0; j < ns[i].size(); j++) {
      segs[i].Set(j, S[ns[i][j]]);
    }
    segs[i].Build();
  }


  scanf("%d", &Q);
  while(Q--) {
    int q;
    scanf("%d", &q);
    if(q == 0) {
      int x, y, z;
      scanf("%d %d %d", &x, &y, &z);
      update(--x, --y, z);
    } else {
      int x, y;
      scanf("%d %d", &x, &y);
      printf("%d\n", dist(--x, --y));
    }
  }
}
0