結果
| 問題 | No.2676 A Tourist |
| ユーザー |
 umimel
|
| 提出日時 | 2024-03-16 14:33:03 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,108 ms / 5,000 ms |
| コード長 | 7,096 bytes |
| コンパイル時間 | 2,530 ms |
| コンパイル使用メモリ | 197,824 KB |
| 実行使用メモリ | 66,900 KB |
| 最終ジャッジ日時 | 2024-09-30 03:59:25 |
| 合計ジャッジ時間 | 18,114 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 31 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;using pll = pair<ll, ll>;#define drep(i, cc, n) for (ll i = (cc); i <= (n); ++i)#define rep(i, n) drep(i, 0, n - 1)#define all(a) (a).begin(), (a).end()#define pb push_back#define fi first#define se secondmt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());const ll MOD1000000007 = 1000000007;const ll MOD998244353 = 998244353;const ll MOD[3] = {999727999, 1070777777, 1000000007};const ll LINF = 1LL << 60LL;const int IINF = (1 << 30) - 1;template<typename T>struct edge{int from, to;T cost;int id;edge(){}edge(int to, T cost=1) : from(-1), to(to), cost(cost){}edge(int to, T cost, int id) : from(-1), to(to), cost(cost), id(id){}edge(int from, int to, T cost, int id) : from(from), to(to), cost(cost), id(id){}};template<typename T>struct redge{int from, to;T cap, cost;int rev;redge(int to, T cap, T cost=(T)(1)) : from(-1), to(to), cap(cap), cost(cost){}redge(int to, T cap, T cost, int rev) : from(-1), to(to), cap(cap), cost(cost), rev(rev){}};template<typename T> using Edges = vector<edge<T>>;template<typename T> using weighted_graph = vector<Edges<T>>;template<typename T> using tree = vector<Edges<T>>;using unweighted_graph = vector<vector<int>>;template<typename T> using residual_graph = vector<vector<redge<T>>>;template<typename W>struct vertex_add_path_sum{struct segtree{int n;vector<W> dat;segtree(){};segtree(int n_){n = 1;while(n < n_) n*=2;dat.resize(2*n, 0);}void update(int k, W a){k += n-1;dat[k] += a;while(k > 0){k = (k-1)/2;dat[k] = dat[2*k+1]+dat[2*k+2];}}// sum of [a, b)W query(int a, int b){return query_sub(a, b, 0, 0, n);}W query_sub(int a, int b, int k, int l, int r){if(r <= a || b <= l){return 0;}else if(a <= l && r <= b){return dat[k];}else{W vl = query_sub(a, b, 2*k+1, l, (l+r)/2);W vr = query_sub(a, b, 2*k+2, (l+r)/2, r);return vl+vr;}}} seg;struct lowest_common_ancestor{int root = 0;int n;int log_n = 1;vector<vector<int>> par;vector<int> depth;lowest_common_ancestor(){}lowest_common_ancestor(tree<W> &T, int root = 0) : root(root){n = (int)T.size();while((1 << log_n) < n) log_n++;par.resize(log_n, vector<int>(n, -1));depth.resize(n, 0);init(T);}void init(tree<W> &T){function<void(int, int)> dfs = [&](int v, int p){par[0][v] = p;for(edge<W> e : T[v]) if(e.to!=p){depth[e.to] = depth[v]+1;dfs(e.to, v);}}; dfs(root, -1);for(int k=0; k+1<log_n; k++){for(int v=0; v<n; v++){if(par[k][v]<0) par[k+1][v] = -1;else par[k+1][v] = par[k][par[k][v]];}}}int query(int u, int v){if(depth[u] < depth[v]) swap(u, v);for(int k=0; k<log_n; k++) if((depth[u]-depth[v]) >> k & 1) u = par[k][u];if(u == v) return u;for(int k=log_n-1; k>=0; k--){if(par[k][u] != par[k][v]){u = par[k][u];v = par[k][v];}}return par[0][u];}} lca;int n;vector<int> par;vector<int> pos;vector<int> depth;vector<int> path_top;vertex_add_path_sum(tree<W> &T, int root = 0){n = (int)T.size();par.resize(n, 0);pos.resize(n, 0);depth.resize(n, 0);path_top.resize(n, -1);init(T, root);}void init(tree<W> &T, int root){vector<int> siz(n, 1);//par, siz, depthを計算function<void(int, int)> dfs1 = [&](int v, int p){par[v] = p;for(edge<W> e : T[v]) if(e.to!=p){depth[e.to] = depth[v]+1;dfs1(e.to, v);siz[v] += siz[e.to];}}; dfs1(root, -1);//heavy-light decompositionint cnt = 0;function<void(int, int, int)> dfs2 = [&](int v, int p, int a){pos[v] = cnt++;path_top[v] = a;int M = 0;int ch = -1;for(edge<W> e : T[v]) if(e.to!=p){if(siz[e.to] > M){M = siz[e.to];ch = e.to;}}if(ch!=-1) dfs2(ch, v, a);for(edge<W> e : T[v]) if(e.to!=p && e.to!=ch) dfs2(e.to, v, e.to);};dfs2(root, -1, root);seg = segtree(n);lca = lowest_common_ancestor(T, root);}vector<pair<int, int>> hld_query(int u, int v){vector<pair<int, int>> ret;int r = lca.query(u, v);while(path_top[u] != path_top[r]){ret.push_back({pos[path_top[u]], pos[u]});u = par[path_top[u]];}while(path_top[v] != path_top[r]){ret.push_back({pos[path_top[v]], pos[v]});v = par[path_top[v]];}ret.push_back({min(pos[u], pos[v]), max(pos[u], pos[v])});return ret;}void update(int v, W x){seg.update(pos[v], x);}W query(int u, int v){vector<pair<int, int>> hld = hld_query(u, v);W ans = 0;for(pair<int, int> p : hld) ans += seg.query(p.fi, p.se+1);return ans;}};void solve(){int n, q; cin >> n >> q;vector<ll> a(n+1, 0);for(int i=0; i<n; i++) cin >> a[i];tree<ll> T(n+1);T[0].push_back(edge<ll>(n));T[n].push_back(edge<ll>(0));for(int i=0; i<n-1; i++){int u, v; cin >> u >> v;u--; v--;T[u].push_back(edge<ll>(v));T[v].push_back(edge<ll>(u));}vertex_add_path_sum<ll> hld(T, n);//初期化function<void(int, int)> dfs = [&](int v, int p){ll sum = 0;for(edge<ll> e : T[v]) if(e.to != p){sum += a[e.to];dfs(e.to, v);}hld.update(v, sum);}; dfs(n, -1);while(q--){int type; cin >> type;if(type==0){int v, x; cin >> v >> x;v--;hld.update(hld.par[v], x);a[v] += x;}if(type==1){int u, v; cin >> u >> v;u--; v--;int r = hld.lca.query(u, v);cout << hld.query(u, v) + a[r] + a[hld.par[r]] << '\n';}}}int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int T=1;//cin >> T;while(T--) solve();}