(luogu2590)树的统计(ZJOI2008) 发表于 2018-02-01 | 分类于 solution , 树相关 , 树链剖分 当是个树剖模板题吧… 树链剖分笔记索引 思路:树剖+线段树 两个查询都是线段树的标准操作, 所以没啥难度 代码:123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161#include <iostream>#include <cstdio>#include <string>#include <algorithm>using namespace std;const int Mn(30005);int n;struct edge //同样的边表{ int e,nt;}ed[Mn*2];int vs[Mn],v[Mn],ec(0);void adde(int s,int e){ ed[++ec].e = e; ed[ec].nt = vs[s]; vs[s] = ec;}int sz[Mn],hs[Mn],pa[Mn],dp[Mn]; //同样的子树大小, 重儿子, 父节点, 深度void dfs1(int x) //找重儿子并更新size{ sz[x] = 1; for(int e(vs[x]);e;e=ed[e].nt) { int& ntn(ed[e].e); if(!dp[ntn]) { dp[ntn] = dp[x]+1; pa[ntn] = x; dfs1(ntn); sz[x] += sz[ntn]; if(sz[hs[x]]<sz[ntn]) hs[x] = ntn; } }}int dc(0),vp[Mn],tp[Mn],a[Mn]; //时间戳, 访问时间, 链顶, 树剖序列void dfs2(int x) //拉重链{ a[++dc] = v[x]; vp[x] = dc; if(hs[x]) { tp[hs[x]] = tp[x]; dfs2(hs[x]); } for(int e(vs[x]);e;e=ed[e].nt) { int& ntn(ed[e].e); if(dp[ntn]>dp[x] && ntn!=hs[x]) { tp[ntn] = ntn; dfs2(ntn); } }}struct sn //线段树结点{ int l,r,sm,mx;}t[Mn<<2];void bud(int l,int r,int rt) //建线段树{ sn& nd(t[rt]),&ls(t[rt<<1]),&rs(t[rt<<1|1]); if(l==r) { nd.l=nd.r=l; nd.sm=nd.mx=a[l]; return; } int mid((l+r)>>1); bud(l,mid,rt<<1); bud(mid+1,r,rt<<1|1); nd.l=l, nd.r=r; nd.sm = ls.sm+rs.sm; nd.mx = max(ls.mx,rs.mx);}void mdf(int rt,int p,int x) //修改{ sn& nd(t[rt]),&ls(t[rt<<1]),&rs(t[rt<<1|1]); if(nd.l==nd.r) { nd.sm=nd.mx=x; return; } if(p<=ls.r) mdf(rt<<1,p,x); else mdf(rt<<1|1,p,x); nd.sm = ls.sm+rs.sm; nd.mx = max(ls.mx,rs.mx);}int qrysm(int rt,int ql,int qr) //查询和{ sn& nd(t[rt]),&ls(t[rt<<1]),&rs(t[rt<<1|1]); if(ql<=nd.l && qr>=nd.r) return nd.sm; int ret(0); if(ql<=ls.r) ret += qrysm(rt<<1,ql,qr); if(qr>=rs.l) ret += qrysm(rt<<1|1,ql,qr); return ret;}int qrymx(int rt,int ql,int qr) //查询最大值{ sn& nd(t[rt]),&ls(t[rt<<1]),&rs(t[rt<<1|1]); if(ql<=nd.l && qr>=nd.r) return nd.mx; int ret(-2333333); if(ql<=ls.r) ret = max(ret,qrymx(rt<<1,ql,qr)); if(qr>=rs.l) ret = max(ret,qrymx(rt<<1|1,ql,qr)); return ret;}int main(){ ios::sync_with_stdio(false); cin >> n; for(int i(1);i<n;++i) { int x,y; cin >> x >> y; adde(x,y), adde(y,x); } for(int i(1);i<=n;++i) cin >> v[i]; dp[1]=1, pa[1]=1; dfs1(1); tp[1]=1; dfs2(1); bud(1,n,1); int q; cin >> q; while(q--) { string opr; int x,y; cin >> opr >> x >> y; if(opr=="QMAX") { int ans(-2333333); while(tp[x]!=tp[y]) //边找LCA边求解 { if(dp[tp[x]]<dp[tp[y]]) swap(x,y); ans = max(ans,qrymx(1,vp[tp[x]],vp[x])); x = pa[tp[x]]; } if(dp[x]<dp[y]) swap(x,y); ans = max(ans,qrymx(1,vp[y],vp[x])); //最后还有一段 cout << ans << endl; } else if(opr=="QSUM") { int ans(0); while(tp[x]!=tp[y]) //同上 { if(dp[tp[x]]<dp[tp[y]]) swap(x,y); ans += qrysm(1,vp[tp[x]],vp[x]); x = pa[tp[x]]; } if(dp[x]<dp[y]) swap(x,y); ans += qrysm(1,vp[y],vp[x]); cout << ans << endl; } else if(opr=="CHANGE") mdf(1,vp[x],y); } return 0;}