题目描述 一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。 我们将以下面的形式来要求你对这棵树完成一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身 输入格式 输入文件的第一行为一个整数n，表示节点的个数。 接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。 接下来一行n个整数，第i个整数wi表示节点i的权值。 接下来1行，为一个整数q，表示操作的总数。 接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。 输出格式 对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。
输入输出样例 输入 #1 4 1 2 2 3 4 1 4 2 1 3 12 QMAX 3 4 QMAX 3 3 QMAX 3 2 QMAX 2 3 QSUM 3 4 QSUM 2 1 CHANGE 1 5 QMAX 3 4 CHANGE 3 6 QMAX 3 4 QMAX 2 4 QSUM 3 4
输出 #1 4 1 2 2 10 6 5 6 5 16
说明/提示 对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。
解释：树链剖分的模板题，剖分完后就是线段树操作了…
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define lson rt<<1 #define rson rt<<1|1 #define ll long long const ll N=2e5+5,M=4e5+5; const ll inf=-100000009; using namespace std; ll n,idx,dfn[N],seq[N],fa[N],dep[N],top[N],sz[N],hvy[N]; ll tree[N]={0},seg[N<<2]={0},val[N]={0}; ll tot,lnk[N],ter[M],nxt[M]; void add(ll u,ll v) { ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot; } void dfs1(ll u,ll f) { fa[u]=f,dep[u]=dep[f]+1,sz[u]=1,hvy[u]=top[u]=0; for(ll i=lnk[u];i;i=nxt[i]) { ll v=ter[i]; if(v==f) continue; dfs1(v,u); sz[u]+=sz[v]; if(sz[hvy[u]]<sz[v]) hvy[u]=v; } } void dfs2(ll u,ll tp) { dfn[u]=++idx,seq[idx]=u,top[u]=tp; if(!hvy[u]) return; dfs2(hvy[u],tp); for(ll i=lnk[u];i;i=nxt[i]) { ll v=ter[i]; if(v==fa[u]||v==hvy[u]) continue; dfs2(v,v); } } void pushup(ll rt) { seg[rt]=max(seg[lson],seg[rson]); tree[rt]=tree[lson]+tree[rson]; } void build(ll rt,ll l,ll r) { if(l==r) { seg[rt]=val[seq[l]]; tree[rt]=val[seq[l]]; return; } ll mid=(l+r)>>1; build(lson,l,mid); build(rson,mid+1,r); pushup(rt); } void modify(ll x,ll rt,ll l,ll r,ll val) { if(l==r){ seg[rt]=val; tree[rt]=val; return; } ll mid=(l+r)>>1; if(x<=mid) modify(x,lson,l,mid,val); else modify(x,rson,mid+1,r,val); pushup(rt); } ll queryMAX(ll x,ll y,ll rt,ll l,ll r){ if(x>y) return inf; if(x<=l&&r<=y) return seg[rt]; ll mid=(l+r)>>1; ll res=inf; if(x<=mid) res=max(res,queryMAX(x,y,lson,l,mid)); if(mid<y) res=max(res,queryMAX(x,y,rson,mid+1,r)); return res; } ll chainQueryMAX(ll u,ll v) { ll res=inf; for(ll fu=top[u],fv=top[v];fu^fv;u=fa[fu],fu=top[u]){ if(dep[fu]<dep[fv]) swap(u,v),swap(fu,fv); res=max(res,queryMAX(dfn[fu],dfn[u],1,1,n)); } if(dep[u]>dep[v]) swap(u,v); res=max(res,queryMAX(dfn[u],dfn[v],1,1,n)); return res; } ll querySUM(ll x,ll y,ll rt,ll l,ll r){ if(x>y) return 0; if(x<=l&&r<=y) return tree[rt]; ll mid=(l+r)>>1; ll res=0; if(x<=mid) res+=querySUM(x,y,lson,l,mid); if(mid<y) res+=querySUM(x,y,rson,mid+1,r); return res; } ll chainQuerySUM(ll u,ll v) { ll res=0; for(ll fu=top[u],fv=top[v];fu^fv;u=fa[fu],fu=top[u]){ if(dep[fu]<dep[fv]) swap(u,v),swap(fu,fv); res+=querySUM(dfn[fu],dfn[u],1,1,n); } if(dep[u]>dep[v]) swap(u,v); res+=querySUM(dfn[u],dfn[v],1,1,n); return res; } int main(){ scanf("%lld",&n); for(int i=1;i<n;++i){ ll u,v; scanf("%lld%lld",&u,&v); add(u,v),add(v,u); } for(ll i=1;i<=n;i++) scanf("%lld",&val[i]); dfs1(1,0),dfs2(1,1),build(1,1,n); ll q=0;scanf("%lld",&q); while(q--){ char cmd[123];scanf("%s",cmd); if(cmd[1]=='H'){ ll u=0; ll t=0; scanf("%lld%lld",&u,&t); modify(dfn[u],1,1,n,t); }else if(cmd[1]=='M'){ ll u=0,v=0;scanf("%lld%lld",&u,&v); printf("%lld\n",chainQueryMAX(u,v)); }else if(cmd[1]=='S'){ ll u=0,v=0;scanf("%lld%lld",&u,&v); printf("%lld\n",chainQuerySUM(u,v)); } } return 0; }