树链剖分-苹果树

1009苹果树

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>#define int long long
#define double long double
#define ull unsigned long long
#define fi first 
#define se second
#define ls(p) p<<1
#define rs(p) (p<<1)|1
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define Yes cout<<"Yes\n"
#define No cout<<"No\n"
#define sp(x) fixed << setprecision(x)
#define all(v) v.begin(),v.end()using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull rnd() { return (unsigned long long)rng(); }const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 5;
int n,m;
vector<int>g[N];
int tr[N],a[N];
int dep[N], sz[N], top[N], fa[N], son[N];
int id[N],nw[N];
int tag[N];
int cnt = 0;
int idx = 0;void init(){cnt = 0;idx = 0;for(int i=1;i<=n;i++){g[i].clear();dep[i] = 0;sz[i] = 0;top[i] = 0;fa[i] = 0;son[i] = 0;tag[i] = 0;id[i] = 0;nw[i] = 0;}return;
}void dfs1(int x,int father,int depth){dep[x] = depth;fa[x] = father;sz[x] = 1;for(const auto &y:g[x]){if(y == father)continue;dfs1(y , x , depth + 1);sz[x] += sz[y];if(sz[son[x]] < sz[y])son[x] = y;}
}void dfs2(int x,int t){id[x] = ++ cnt;nw[cnt] = a[x];top[x] = t;if(!son[x])return;dfs2(son[x] , t);for(const auto &y:g[x]){if(y == fa[x] || y == son[x])continue;dfs2(y,y);}return;
}void push_up(int p){tr[p] = max(tr[ls(p)] , tr[rs(p)]);
}void build(int p,int l,int r){if(l == r){tr[p] = nw[l];return;}int mid = l+r>>1;build(ls(p) , l , mid);build(rs(p) , mid + 1 , r);push_up(p);
}int query(int p,int l,int r,int nl,int nr){if(nl <= l && r <= nr){return tr[p];}int mid = l+r>>1;int res = 0;if(nl <= mid)res = query(ls(p) , l , mid , nl , nr);if(nr > mid)res = max(res , query(rs(p) , mid+1 , r , nl , nr));return res;
}void update(int p,int l,int r,int x,int k){if(l == r){tr[p] += k; return;}int mid = l + r >> 1;if(x <= mid)update(ls(p) , l , mid , x , k);else update(rs(p) , mid + 1 , r , x , k);push_up(p);return;
}int query_path(int x,int y){int res = 0;while(top[x] != top[y]){if(dep[top[x]] < dep[top[y]])swap(x , y);res = max(res , query(1 , 1 , n , id[top[x]] , id[x]));res = max(res , a[top[x]] + tag[fa[top[x]]]);x = fa[top[x]];}if(dep[x] > dep[y])swap(x , y);res = max(res , query(1 , 1 , n , id[x] , id[y]));if(x == top[x])res = max(res , a[x] + tag[fa[x]]);return res;
}void solve(){cin>>n>>m;init();for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<n;i++){int x,y;cin>>x>>y;g[x].push_back(y);g[y].push_back(x);}dfs1(1,-1,1);dfs2(1,1);build(1,1,n);while(m -- ){int op;cin>>op;if(op == 1){int x,y;cin>>x>>y;cout<<query_path(x , y)<<"\n";}else{int x,k;cin>>x>>k;tag[x] += k;if(fa[x] > 0){update(1 , 1 , n , id[fa[x]] , k);a[fa[x]] += k;}   if(son[x] > 0){update(1 , 1 , n , id[son[x]] , k);a[son[x]] += k;}}}}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);time_t Start = clock();int T = 1;cin >> T;while (T -- ){solve();}time_t End = clock(); time_t Run_time = End - Start;//cout<<"\n"<<Run_time<<"ms"<<"\n"; return 0;
}