P2590 [ZJOI2008]樹的統計

題目描述

一棵樹上有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 MAXN 1000000 using namespace std; int n,q,sz,tot; int w[MAXN],id[MAXN]; int dad[MAXN],deep[MAXN],size[MAXN],top[MAXN]; int to[MAXN],head[MAXN],net[MAXN]; struct nond{int l,r,dis,sum; }tree[MAXN]; void add(int u,int v){to[++tot]=v;net[tot]=head[u];head[u]=tot;to[++tot]=u;net[tot]=head[v];head[v]=tot; } void up(int now){tree[now].sum=tree[now*2].sum+tree[now*2+1].sum;tree[now].dis=max(tree[now*2].dis,tree[now*2+1].dis); } void build(int now,int l,int r){tree[now].l=l;tree[now].r=r;if(tree[now].l==tree[now].r)return ;int mid=(tree[now].l+tree[now].r)/2;build(now*2,l,mid);build(now*2+1,mid+1,r); } void change(int now,int x,int k){if(tree[now].l==tree[now].r){tree[now].dis=k;tree[now].sum=k;return ;}int mid=(tree[now].l+tree[now].r)/2;if(x<=mid) change(now*2,x,k);else if(x>mid) change(now*2+1,x,k);up(now); } int query(int now,int l,int r,int z){if(tree[now].l==l&&tree[now].r==r){if(z==1) return tree[now].dis;else if(z==0) return tree[now].sum;}int mid=(tree[now].l+tree[now].r)/2;if(r<=mid) return query(now*2,l,r,z);else if(l>mid) return query(now*2+1,l,r,z);else{if(z==1)return max(query(now*2,l,mid,z),query(now*2+1,mid+1,r,z));else if(z==0)return query(now*2,l,mid,z)+query(now*2+1,mid+1,r,z);} } void dfs(int x){size[x]=1;deep[x]=deep[dad[x]]+1;for(int i=head[x];i;i=net[i])if(dad[x]!=to[i]){dad[to[i]]=x;dfs(to[i]);size[x]+=size[to[i]];} } void dfs1(int x){int t=0;id[x]=++sz;if(!top[x]) top[x]=x;change(1,sz,w[x]);for(int i=head[x];i;i=net[i])if(dad[x]!=to[i]&&size[t]<size[to[i]])t=to[i];if(t){top[t]=top[x];dfs1(t);}for(int i=head[x];i;i=net[i])if(dad[x]!=to[i]&&t!=to[i])dfs1(to[i]); } int squery(int x,int y,int z){int ans;if(z==1) ans=-0x7f7f7f7f;else ans=0;while(top[x]!=top[y]){if(deep[top[x]]<deep[top[y]]) swap(x,y);if(z==1) ans=max(ans,query(1,id[top[x]],id[x],1));else ans+=query(1,id[top[x]],id[x],0);x=dad[top[x]];}if(id[x]>id[y]) swap(x,y);if(z==1) ans=max(ans,query(1,id[x],id[y],1));else ans+=query(1,id[x],id[y],0);return ans; } int main(){scanf("%d",&n);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);add(u,v);}for(int i=1;i<=n;i++)scanf("%d",&w[i]);build(1,1,n);dfs(1);dfs1(1);scanf("%d",&q);for(int i=1;i<=q;i++){char a[10];int u,v;scanf("%s%d%d",a,&u,&v);if(a[1]=='H')change(1,id[u],v);else if(a[1]=='M')printf("%d\n",squery(u,v,1));elseprintf("%d\n",squery(u,v,0));} }

?

轉載于:https://www.cnblogs.com/cangT-Tlan/p/7404486.html

總結

以上是生活随笔為你收集整理的洛谷 P2590 [ZJOI2008]树的统计的全部內容，希望文章能夠幫你解決所遇到的問題。

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