Code:
#include#include #include using namespace std;typedef long long ll;const int maxn=30000+5;int head[maxn],nex[maxn*2],to[maxn*2]; int dep[maxn],siz[maxn],son[maxn],p[maxn],top[maxn];int A[maxn],maxv[maxn*4+3], val[maxn]; int val2[maxn]; ll sumv[maxn*4+3]; int _max; int cnt,n,cnt2;void addedge(int u,int v){ nex[++cnt]=head[u]; head[u]=cnt,to[cnt]=v;}void dfs1(int u,int fa,int cur){ p[u]=fa,dep[u]=cur,siz[u]=1; for(int i=head[u];i;i=nex[i]) { int v=to[i]; if(v!=fa) { dfs1(v,u,cur+1); siz[u]+=siz[v]; if(son[u]==-1||siz[v]>siz[son[u]])son[u]=v; } }}void dfs2(int u,int tp){ top[u]=tp,A[u]=++cnt2; if(son[u]>0)dfs2(son[u],tp); for(int i=head[u];i;i=nex[i]) { int v=to[i]; if(v!=p[u]&&v!=son[u])dfs2(v,v); }}void build_tree(int L,int R,int o,int arr[]){ if(L==R){ sumv[o]=maxv[o]=arr[L]; return; } int mid=(L+R)/2; build_tree(L,mid,o*2,arr); build_tree(mid+1,R,o*2+1,arr); sumv[o]=sumv[o*2]+sumv[o*2+1]; maxv[o]=max(maxv[o*2],maxv[o*2+1]);}void update(int l,int k,int L,int R,int o){ if(L==R) { sumv[o]=maxv[o]=k; return; } int mid=(L+R)/2; if(l<=mid)update(l,k,L,mid,o*2); else update(l,k,mid+1,R,o*2+1); sumv[o]=sumv[o*2]+sumv[o*2+1]; maxv[o]=max(maxv[o*2],maxv[o*2+1]);}ll query(int l,int r,int L,int R,int o){ if(l<=L&&r>=R) { _max=max(_max,maxv[o]); return sumv[o]; } int mid=(L+R)/2; ll ret=0; if(l<=mid)ret+=query(l,r,L,mid,o*2); if(r>mid)ret+=query(l,r,mid+1,R,o*2+1); return ret;}ll lca(int x,int y) { _max=-300000; ll ret=0; while(top[x]!=top[y]) { if(dep[top[x]]