Description

　　一棵樹上有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本身

Input

　　輸入文件的第一行為一個整數n，表示節點的個數。
　　接下來n – 1行，每行2個整數a和b，表示節點a和節點b之間有一條邊相連。
　　接下來n行，每行一個整數，第i行的整數wi表示節點i的權值。
　　接下來1行，為一個整數q，表示操作的總數。
　　接下來q行，每行一個操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式給出。

Output

　　對于每個“QMAX”或者“QSUM”的操作，每行輸出一個整數表示要求輸出的結果。

Sample Input

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

Sample Output

4
1
2
2
10
6
5
6
5
16

Hint

【數據說明】

　　對于100％的數據，保證1<=n<=30000，0<=q<=200000；中途操作中保證每個節點的權值w在-30000到30000之間。

Solution

• 這題的操作一看就像線段樹，可是操作卻在樹上，怎么辦呢？

• 于是，我們就要用到一種高級算法——樹鏈剖分！

• 這道題是樹鏈剖分的模板題，操作相對簡單。

• 詳細請見：樹鏈剖分詳解

• 接著套上線段樹就能實現這些詢問了！

• 下見代碼：

Code

#include<cstdio> #include<algorithm> using namespace std; const int N=30001; struct data {int sum,max,l,r; }f[N<<2]; int tot,num; int first[N],next[N<<1],en[N<<1]; int fa[N],dep[N],size[N],son[N],top[N]; int tree[N],pre[N]; int a[N]; char s[7]; inline int read() {int data=0,w=1; char ch=0;while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();if(ch=='-') ch=getchar(),w=-1;while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data*w; } inline void insert(int x,int y) {next[++tot]=first[x];first[x]=tot;en[tot]=y; } inline void dfs1(int x) {dep[x]=dep[fa[x]]+1;size[x]=1;for(int i=first[x];i;i=next[i])if(en[i]!=fa[x]){fa[en[i]]=x;dfs1(en[i]);size[x]+=size[en[i]];if(!son[x] || size[son[x]]<size[en[i]]) son[x]=en[i];} } inline void dfs2(int x,int y) {top[pre[tree[x]=++num]=x]=y;if(!son[x]) return;dfs2(son[x],y);for(int i=first[x];i;i=next[i])if(en[i]!=fa[x] && en[i]!=son[x]) dfs2(en[i],en[i]); } inline int max(int x,int y) {return x>y?x:y; } inline void update(int v) {int ls=v<<1,rs=ls+1;f[v].sum=f[ls].sum+f[rs].sum;f[v].max=max(f[ls].max,f[rs].max); } inline void make(int v,int l,int r) {f[v].l=l,f[v].r=r;if(l==r){f[v].sum=f[v].max=a[pre[l]];return;}int mid=(l+r)>>1;make(v<<1,l,mid);make((v<<1)+1,mid+1,r);update(v); } inline void change(int v,int x,int add) {if(f[v].l==f[v].r){f[v].max+=add;f[v].sum+=add;return;}int mid=(f[v].l+f[v].r)>>1;if(x<=mid) change(v<<1,x,add); else change((v<<1)+1,x,add);update(v); } inline int dfs_max(int v,int x,int y) {if(f[v].l>=x && f[v].r<=y) return f[v].max;int mid=(f[v].l+f[v].r)>>1,mx=-1e9;if(x<=mid) mx=dfs_max(v<<1,x,y);if(y>mid) mx=max(mx,dfs_max((v<<1)+1,x,y));update(v);return mx; } inline int dfs_sum(int v,int x,int y) {if(f[v].l>=x && f[v].r<=y) return f[v].sum;int mid=(f[v].l+f[v].r)>>1,sum=0;if(x<=mid) sum+=dfs_sum(v<<1,x,y);if(y>mid) sum+=dfs_sum((v<<1)+1,x,y);update(v);return sum; } inline int find_max(int x,int y) {int f1=top[x],f2=top[y],ans=-1e9;while(f1!=f2){if(dep[f1]<dep[f2]) swap(f1,f2),swap(x,y);ans=max(ans,dfs_max(1,tree[f1],tree[x]));x=fa[f1],f1=top[x];}if(dep[x]>dep[y]) swap(x,y);ans=max(ans,dfs_max(1,tree[x],tree[y]));return ans; } inline int find_sum(int x,int y) {int f1=top[x],f2=top[y],ans=0;while(f1!=f2){if(dep[f1]<dep[f2]) swap(f1,f2),swap(x,y);ans+=dfs_sum(1,tree[f1],tree[x]);x=fa[f1],f1=top[x];}if(dep[x]>dep[y]) swap(x,y);ans+=dfs_sum(1,tree[x],tree[y]);return ans; } int main() {int n=read();for(int i=1;i<n;i++){int x=read(),y=read();insert(x,y);insert(y,x);}for(int i=1;i<=n;i++) a[i]=read();dfs1(1);dfs2(1,1);make(1,1,n);int q=read();while(q--){scanf("%s",s);int x=read(),y=read();if(s[1]=='H'){change(1,tree[x],y-a[x]);a[x]=y;}else printf("%d\n",s[1]=='M'?find_max(x,y):find_sum(x,y));}return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 2256. 【BZOJ 2256】【ZJOI 2008】树的统计的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。