結果
問題 | No.2676 A Tourist |
ユーザー |
|
提出日時 | 2024-03-15 22:06:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 295 ms / 5,000 ms |
コード長 | 2,422 bytes |
コンパイル時間 | 997 ms |
コンパイル使用メモリ | 82,564 KB |
実行使用メモリ | 35,780 KB |
最終ジャッジ日時 | 2024-09-30 01:20:16 |
合計ジャッジ時間 | 10,007 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>#include<cassert>#include<atcoder/fenwicktree>using namespace std;class HLD{private:void dfs_sz(int v) {auto &es=G[v];if(~par[v]) es.erase(find(es.begin(),es.end(),par[v]));for(int &u:es){par[u]=v;dfs_sz(u);sub[v]+=sub[u];if(sub[u]>sub[es[0]]) swap(u,es[0]);}}void dfs_hld(int v,int &pos) {vid[v]=pos++;inv[vid[v]]=v;for(int u:G[v]){if(u==par[v]) continue;nxt[u]=(u==G[v][0]?nxt[v]:u);dfs_hld(u,pos);}}public:vector< vector<int> > G;// vid: vertex -> idx// inv: idx -> vertexvector<int> vid,nxt,sub,par,inv;HLD(int n):G(n),vid(n,-1),nxt(n),sub(n,1),par(n,-1),inv(n){}void add_edge(int u,int v) {G[u].emplace_back(v);G[v].emplace_back(u);}void build(int r=0) {int pos=0;dfs_sz(r);nxt[r]=r;dfs_hld(r,pos);}int lca(int u,int v){while(1){if(vid[u]>vid[v]) swap(u,v);if(nxt[u]==nxt[v]) return u;v=par[nxt[v]];}}template<typename F>void for_each(int u,int v,const F& f) {while(1){if(vid[u]>vid[v]) swap(u,v);f(max(vid[nxt[v]],vid[u]),vid[v]+1);if(nxt[u]!=nxt[v]) v=par[nxt[v]];else break;}}template<typename F>void for_each_edge(int u,int v,const F& f) {while(1){if(vid[u]>vid[v]) swap(u,v);if(nxt[u]!=nxt[v]){f(vid[nxt[v]],vid[v]+1);v=par[nxt[v]];}else{if(u!=v) f(vid[u]+1,vid[v]+1);break;}}}};long A[2<<17];long S[2<<17];int N,Q;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>N>>Q;for(int i=0;i<N;i++)cin>>A[i];HLD hld(N);for(int i=1;i<N;i++){int u,v;cin>>u>>v;u--,v--;hld.add_edge(u,v);}hld.build(0);for(int i=1;i<N;i++)S[hld.par[i]]+=A[i];atcoder::fenwick_tree<long>BIT(N);for(int i=0;i<N;i++)BIT.add(hld.vid[i],S[i]);for(int i=0;i<Q;i++){int op;cin>>op;if(op==0){int v,x;cin>>v>>x;v--;A[v]+=x;if(v!=0){S[hld.par[v]]+=x;BIT.add(hld.vid[hld.par[v]],x);}}else{int u,v;cin>>u>>v;u--,v--;int w=hld.lca(u,v);long ans=A[w];if(w!=0)ans+=A[hld.par[w]];hld.for_each(w,u,[&](int l,int r){ans+=BIT.sum(l,r);});hld.for_each(w,v,[&](int l,int r){ans+=BIT.sum(l,r);});ans-=S[w];cout<<ans<<"\n";}}}