Submit Info #2640

Problem Lang User Status Time Memory
Vertex Add Path Sum cpp Imperi AC 2167 ms 221.27 MiB

ケース詳細
Name Status Time Memory
almost_line_00 AC 2159 ms 216.40 MiB
almost_line_01 AC 2167 ms 213.66 MiB
example_00 AC 5 ms 0.68 MiB
line_00 AC 2107 ms 211.58 MiB
line_01 AC 2043 ms 221.27 MiB
max_random_00 AC 1524 ms 195.89 MiB
max_random_01 AC 1549 ms 195.86 MiB
max_random_02 AC 1544 ms 195.85 MiB
random_00 AC 1187 ms 156.51 MiB
random_01 AC 1354 ms 182.39 MiB
random_02 AC 324 ms 22.12 MiB
random_03 AC 831 ms 168.09 MiB
random_04 AC 584 ms 114.98 MiB
small_00 AC 5 ms 0.88 MiB
small_01 AC 6 ms 0.63 MiB
small_02 AC 7 ms 0.67 MiB
small_03 AC 6 ms 0.67 MiB
small_04 AC 6 ms 0.84 MiB

#include <cassert> #include <algorithm> #include <bitset> #include <cctype> #include <cmath> #include <complex> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <unordered_map> #include <vector> #include <random> #include <memory> #include <utility> #include <limits> #include "limits.h" #define rep(i, a, b) for (long long (i) = (a); i < (b); i++) #define all(i) i.begin(), i.end() #define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) void debug_out(){std::cerr<<std::endl;} template<typename Head,typename... Tail> void debug_out(Head h,Tail... t){ std::cerr<<" "<<h; debug_out(t...); } template <typename T1, typename T2> std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) { return os << pa.first << " " << pa.second; } template <typename T> std::ostream& operator<<(std::ostream& os, std::vector<T> vec) { for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " "); return os; } template<typename T1,typename T2> inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);} template<typename T1,typename T2> inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);} long long pow_mod(long long a, long long b, long long mod=-1) { if(b==0)return 1; if ((a == 0)||(mod!=-1&&(a+mod)%mod==0)) { return 0; } long long x = 1; while (b > 0) { if (b & 1) { x = (mod!=-1)?(x * a) % mod:x*a; } a = (mod!=-1)?(a * a) % mod:a*a; b >>= 1; } return x; } // const long long MOD = 998244353; const long long MOD = 1e9 + 7; using ll = long long; using P = std::pair<long long, long long>; //LowestCommonAncestor //ダブリングを使う 前処理O(Nlog N),クエリO(log N) class LowestCommonAncestor{ using ll=long long; private: ll n,bit; std::vector<ll> depth; std::vector<std::vector<ll>> par_doubling,graph; ll getbit(ll temp){ ll a=1; while(temp>0){ a++; temp>>=1; } return a; } void dfs(ll now,ll par,ll dep){ depth[now]=dep; if(par!=-1)par_doubling[now][0]=par; else par_doubling[now][0]=now; for(auto e:graph[now]){ if(e!=par){ dfs(e,now,dep+1); } } } void doubling(){ for(ll i=1;i<bit;i++){ for(ll j=0;j<n;j++){ par_doubling[j][i]=par_doubling[par_doubling[j][i-1]][i-1]; } } } public: //隣接リストのグラフと木の根を渡す LowestCommonAncestor(const std::vector<std::vector<ll>>& g,ll root_):graph(g),n(g.size()),bit(getbit(g.size())), depth(n),par_doubling(n,std::vector<ll>(bit)){ dfs(root_,-1,0); doubling(); } ll query(ll a,ll b){ if(depth[a]<depth[b])std::swap(a,b); for(ll i=0;i<bit;i++){ if(((depth[a]-depth[b])>>i)&1)a=par_doubling[a][i]; } if(a==b)return a; for(ll i=bit-1;i>=0;i--){ if(par_doubling[a][i]!=par_doubling[b][i]){ a=par_doubling[a][i]; b=par_doubling[b][i]; } } return par_doubling[a][0]; } }; //非再帰抽象セグ木 0-indexed 単位元はiで指定 template <class T> class SegmentTree { private: using F=std::function<T(T,T)>; long long n; T init; std::vector<T> dat; F fn; public: SegmentTree(long long i, T para, F fun) : init(para), fn(fun) { n = 1; while (n < i) { n *= 2; } dat = std::vector<T>(2 * n - 1, init); } SegmentTree(const std::vector<T>& seq,T para,F fun) : init(para),fn(fun){ n=1; while(n<seq.size())n<<=1; dat=std::vector<T>(2*n-1,init); for(long long i=0;i<seq.size();i++)dat[i+n-1]=seq[i]; for(long long i=n-2;i>=0;i--)dat[i]=fn(dat[i*2+1],dat[i*2+2]); } // k番目(0-indexed)を値aで更新,dest=trueのときは更新前を破壊して初期化する void update(long long k, T a, bool dest) { assert(0<=k&&k<n); k += n - 1; if (dest) dat[k] = a; else dat[k] = fn(dat[k], a); while (k > 0) { k = (k - 1) / 2; dat[k] = fn(dat[k * 2 + 1], dat[k * 2 + 2]); } } //[a,b)の値を返す T query(long long a, long long b){ assert(0<=a&&b<=n); T rval=init,lval=init; long long l=a+n-1,r=b+n-1; for(;l<r;l=(l>>1),r=(r>>1)){ if(!(r&1)){ r--; rval=fn(dat[r],rval); } if(!(l&1)){ lval=fn(lval,dat[l]); l++; } } return fn(lval,rval); } }; int main() { std::cin.tie(0); std::ios::sync_with_stdio(false); ll n,q; std::cin>>n>>q; std::vector<ll> weight(n); std::vector<std::vector<ll>> graph(n); rep(i,0,n)std::cin>>weight[i]; rep(i,0,n-1){ ll u,v; std::cin>>u>>v; graph[u].push_back(v); graph[v].push_back(u); } std::vector<ll> begin(n),end(n),tour; auto f=[&](auto f,ll now,ll par)->void{ begin[now]=tour.size(); tour.push_back(now); for(ll next:graph[now]){ if(next!=par){ f(f,next,now); tour.push_back(now); } } end[now]=tour.size(); }; f(f,0,-1); LowestCommonAncestor lca(graph,0); SegmentTree<ll> seg(2*n,0,[](ll a,ll b){return a+b;}); rep(i,0,n){ seg.update(begin[i],weight[i],false); seg.update(end[i],-weight[i],false); } rep(_,0,q){ ll mode; std::cin>>mode; if(mode==0){ ll p,x; std::cin>>p>>x; seg.update(begin[p],x,false); seg.update(end[p],-x,false); }else{ ll u,v; std::cin>>u>>v; ll lcav=lca.query(u,v); ll ans=-seg.query(begin[lcav],begin[lcav]+1); ans+=seg.query(begin[lcav],begin[u]+1); ans+=seg.query(begin[lcav],begin[v]+1); std::cout<<ans<<"\n"; } } return 0; }