結果

問題 No.235 めぐるはめぐる (5)
ユーザー 0w10w1
提出日時 2020-11-09 20:42:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,253 ms / 10,000 ms
コード長 6,804 bytes
コンパイル時間 3,215 ms
コンパイル使用メモリ 231,736 KB
実行使用メモリ 80,364 KB
最終ジャッジ日時 2024-07-22 16:18:20
合計ジャッジ時間 12,968 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,253 ms
62,788 KB
testcase_01 AC 1,245 ms
80,364 KB
testcase_02 AC 1,953 ms
64,872 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template<typename T>
struct Segt {
  vector<T> dat;
  vector<T> tag;
  vector<T> psm;
  Segt(const vector<T> &a, const vector<T> &p) : psm(p) {
    const int n = a.size();
    dat.assign(n * 4, psm[0]);
    tag.assign(n * 4, psm[0]);
    function<void(int, int, int)> dfs = [&](int lb, int rb, int t) {
      if (rb - lb == 1) return dat[t] = a[lb], void();
      int mb = lb + rb >> 1;
      dfs(lb, mb, t << 1);
      dfs(mb, rb, t << 1 | 1);
      dat[t] = dat[t << 1] + dat[t << 1 | 1];
    };
    dfs(0, n, 1);
  }
  void push(int lb, int rb, int t) {
    int mb = lb + rb >> 1;
    dat[t << 1] += tag[t] * (psm[mb] - psm[lb]);
    tag[t << 1] += tag[t];
    dat[t << 1 | 1] += tag[t] * (psm[rb] - psm[mb]);
    tag[t << 1 | 1] += tag[t];
    tag[t].v = 0;
  }
  void update(T v, int ql, int qr, int lb, int rb, int t = 1) {
    if (qr <= lb || rb <= ql) return;
    if (ql <= lb && rb <= qr) return dat[t] += v * (psm[rb] - psm[lb]), tag[t] += v, void();
    push(lb, rb, t);
    int mb = lb + rb >> 1;
    update(v, ql, qr, lb, mb, t << 1);
    update(v, ql, qr, mb, rb, t << 1 | 1);
    dat[t] = dat[t << 1] + dat[t << 1 | 1];
  }
  T query(int ql, int qr, int lb, int rb, int t = 1) {
    if (qr <= lb || rb <= ql) return T(0, dat[1].m);
    if (ql <= lb && rb <= qr) return dat[t];
    push(lb, rb, t);
    int mb = lb + rb >> 1;
    return query(ql, qr, lb, mb, t << 1) + query(ql, qr, mb, rb, t << 1 | 1);
  }
};

struct Mint {
  int v, m;
  Mint() {}
  Mint(int _v, int _m) : v(_v), m(_m) { v %= m; adjust(); }
  void adjust() { if (v < 0) v += m; if (v >= m) v -= m; assert(0 <= v && v < m); }
  Mint operator+() const { return *this; }
  Mint operator-() const { Mint r = Mint(0, m) - *this; return r.adjust(), r; }
  friend Mint operator+(Mint a, Mint b) { a.v += b.v; return a.adjust(), a; }
  Mint& operator+=(const Mint &b) { return v += b.v, adjust(), *this; }
  friend Mint operator-(Mint a, Mint b) { a.v -= b.v; return a.adjust(), a; }
  Mint& operator-=(const Mint &b) { return v -= b.v, adjust(), *this; }
  friend Mint operator*(Mint a, Mint b) { a.v = (int64_t) a.v * b.v % a.m; return a.adjust(), a; }
  friend Mint operator/(Mint a, Mint b) {
    int u = 1;
    for (int i = a.m - 2; i; i >>= 1) {
      if (i & 1) u = (int64_t) u * b.v % a.m;
      b.v = (int64_t) b.v * b.v % a.m;
    }
    return a * Mint(u, a.m);
  }
};

struct LCA {
  vector<int> dpt;
  vector<vector<int>> par;
  LCA() {} 
  LCA(const vector<vector<int>> &g, int root) {
    int n = g.size();
    int lgn = 32 - __builtin_clz(n);
    dpt.resize(n);
    par.assign(lgn, vector<int>(n, -1));
    function<void(int, int)> dfs = [&](int u, int fa) {
      for (int v : g[u]) if (v != fa) {
        dpt[v] = dpt[u] + 1;
        par[0][v] = u;
        dfs(v, u);
      }
    };
    dfs(root, -1);
    for (int i = 0; i + 1 < lgn; ++i) {
      for (int u = 0; u < n; ++u) {
        int p = par[i][u];
        if (~p) par[i + 1][u] = par[i][p];
      }
    }
  }
  int query(int u, int v) {
    if (dpt[u] > dpt[v]) swap(u, v);
    for (int i = par.size() - 1; ~i; --i) if (dpt[v] - dpt[u] >= 1 << i) {
      v = par[i][v];
    }
    if (u == v) return u;
    for (int i = par.size() - 1; par[0][u] != par[0][v]; --i) {
      if (par[i][u] != par[i][v]) {
        u = par[i][u];
        v = par[i][v];
      }
    }
    assert(par[0][u] == par[0][v]);
    return par[0][u];
  }
};

template<typename E>
struct HLD {
  LCA lca;
  vector<int> par;
  vector<int> idxInPath;
  vector<int> belongsToPath;
  vector<vector<int>> paths;
  HLD(const vector<vector<int>> &g) {
    lca = LCA(g, 0);
    const int n = g.size();
    idxInPath.resize(n);
    belongsToPath.resize(n);
    function<int(int, int)> dfs = [&](int u, int fa) {
      int size = 1;
      pair<int, int> maxchsize(0, -1);
      for (int v : g[u]) if (v != fa) {
        int chsize = dfs(v, u);
        size += chsize;
        maxchsize = max(maxchsize, make_pair(chsize, v));
      }
      int heavyNode = maxchsize.second;
      if (heavyNode == -1) {
        par.push_back(fa);
        idxInPath[u] = 0;
        belongsToPath[u] = paths.size();
        paths.emplace_back();
        paths.back().push_back(u);
      } else {
        int x = belongsToPath[heavyNode];
        par[x] = fa;
        belongsToPath[u] = x;
        idxInPath[u] = paths[x].size();
        paths[x].push_back(u);
      }
      return size;
    };
    dfs(0, -1);
  }
  void updatePath(E q, int u, int v, vector<Segt<Mint>> &st) {
    int w = lca.query(u, v);
    function<void(E, int, int)> _updatePath = [&](E w, int p, int q) {
      int bp = belongsToPath[p];
      int bq = belongsToPath[q];
      if (bp == bq) {
        st[bp].update(w, idxInPath[p], idxInPath[q] + 1, 0, paths[bp].size());
      } else {
        st[bp].update(w, idxInPath[p], paths[bp].size(), 0, paths[bp].size());
        _updatePath(w, par[bp], q);
      }
    };
    _updatePath(+q, u, w);
    _updatePath(+q, v, w);
    _updatePath(-q, w, w);
  }
  E queryPath(int u, int v, vector<Segt<Mint>> &st) {
    int w = lca.query(u, v);
    function<E(int, int)> _queryPath = [&](int p, int q) {
      int bp = belongsToPath[p];
      int bq = belongsToPath[q];
      if (bp == bq) return st[bp].query(idxInPath[p], idxInPath[q] + 1, 0, paths[bp].size());
      return st[bp]
        .query(idxInPath[p], paths[bp].size(), 0, paths[bp].size())
        + _queryPath(par[bp], q);
    };
    return _queryPath(u, w) + _queryPath(v, w) - _queryPath(w, w);
  }
};

int main() {
  ios::sync_with_stdio(false);

  int N; { cin >> N; }

  vector<int> S(N); 
  vector<int> C(N); 
  vector<vector<int>> G(N); {
    for (int i = 0; i < N; ++i) cin >> S[i];
    for (int i = 0; i < N; ++i) cin >> C[i];
    for (int i = 0; i + 1 < N; ++i) {
      int U, V;
      cin >> U >> V;
      G[U - 1].push_back(V - 1);
      G[V - 1].push_back(U - 1);
    }
  }

  const int M = 1e9 + 7;

  HLD<Mint> hld(G);
  vector<Segt<Mint>> segts; {
    for (int i = 0; i < hld.paths.size(); ++i) {
      vector<Mint> pc(hld.paths[i].size() + 1); {
        pc[0] = Mint(0, M);
        for (int j = 0; j < hld.paths[i].size(); ++j) {
          pc[j + 1].v = C[hld.paths[i][j]];
          pc[j + 1].m = M;
          pc[j + 1] += pc[j];
        }
      }
      vector<Mint> vec(hld.paths[i].size()); {
        for (int j = 0; j < vec.size(); ++j) {
          vec[j].v = S[hld.paths[i][j]];
          vec[j].m = M;
        }
      }
      segts.emplace_back(vec, pc);
    }
  }

  int Q; { cin >> Q; }
  while (Q--) {
    int P; { cin >> P; }
    if (P == 0) {
      int X, Y, Z; { cin >> X >> Y >> Z; --X, --Y; }
      hld.updatePath(Mint(Z, M), X, Y, segts);
    } else {
      int X, Y; { cin >> X >> Y; --X, --Y; }
      cout << hld.queryPath(X, Y, segts).v << "\n";
    }
  }
}
0