鏈接：點擊打開鏈接

題意：給出一顆樹，和樹上每個節點的權值，有三種操作，分別為把C1與C2的路徑上的所有點的權值加K，把C1與C2的路徑上的所有點的權值減K，和詢問c節點的權值

代碼：

//#pragma comment(linker, "/STACK:1024000000,1024000000") #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; const int SIZE=50005; int n,m,q,tim; int sum[4*SIZE],add[4*SIZE]; //sum為線段樹,add為懶惰標記 int num[SIZE],siz[SIZE],top[SIZE],son[SIZE]; //num為節點的權值，fa為父節點，son為重兒子，top為重鏈的第一個節點 int dep[SIZE],tid[SIZE],ran[SIZE],fa[SIZE]; //dep為節點深度，tid為節點剖分后的編號，ran為剖分后的新編號實際的點 int head[SIZE],to[2*SIZE],nex[2*SIZE],edge; //siz為以當前節點為根節點的子樹含的節點數 void addedge(int u,int v){to[edge]=v,nex[edge]=head[u],head[u]=edge++;//基本定義：to[edge]=u,nex[edge]=head[v],head[v]=edge++;//重兒子：當前節點中siz最大的就為當前節點的重兒子 } //重邊：節點與其重兒子的連邊 void dfs1(int u,int father,int d){ //重鏈：重變連成的路徑int i,v; //因為邊數可能很多因此用前向星建圖fa[u]=father; //因為我們要分解出所有的重鏈因此，需要知道每個節點的重兒子 dep[u]=d; //同時求出父節點和節點的深度，用于后續查詢時使用 siz[u]=1;for(i=head[u];~i;i=nex[i]){v=to[i];if(v!=father){ //每條邊都是雙向邊，因此v!=fatherdfs1(v,u,d+1);siz[u]+=siz[v];if(son[u]==-1||siz[v]>siz[son[u]]) //沒有重兒子或則新的節點的siz大于原來的sizson[u]=v; //更新重兒子 }} } void dfs2(int u,int tp){int i,v;top[u]=tp;tid[u]=tim++; //將節點重新編號，同一條重鏈上的點放在維護的ran[tid[u]]=u; //的數據結構中連續的空間內，從而才能實現高效if(son[u]==-1) //的查詢和詢問return;dfs2(son[u],tp); //根據dfs1找出的重兒子從而找出重鏈for(i=head[u];~i;i=nex[i]){v=to[i];if(v!=son[u]&&v!=fa[u])dfs2(v,v); //新的重鏈} } void pushdown(int rt,int m){ //線段樹區間更新if(add[rt]){add[rt<<1]+=add[rt];add[rt<<1|1]+=add[rt];sum[rt<<1]+=(m-(m>>1))*add[rt];sum[rt<<1|1]+=(m>>1)*add[rt];add[rt]=0;} } void build(int l,int r,int rt){int m;add[rt]=0;if(l==r){sum[rt]=num[ran[l]];return;}m=(l+r)>>1;build(l,m,rt<<1);build(m+1,r,rt<<1|1);sum[rt]=max(sum[rt],sum[rt<<1|1]); } void update(int L,int R,int p,int l,int r,int rt){int m;if(L<=l&&r<=R){add[rt]+=p;sum[rt]+=(r-l+1)*p;return;}pushdown(rt,r-l+1);m=(l+r)>>1;if(L<=m)update(L,R,p,l,m,rt<<1);if(R>m)update(L,R,p,m+1,r,rt<<1|1);sum[rt]=max(sum[rt<<1],sum[rt<<1|1]); } int query(int p,int l,int r,int rt){int m,ans;ans=0;if(l==r)return sum[rt];pushdown(rt,r-l+1);m=(l+r)>>1;if(p<=m)ans=query(p,l,m,rt<<1);elseans=query(p,m+1,r,rt<<1|1);sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);return ans; } void change(int x,int y,int p){ //對這顆樹進行更新 while(top[x]!=top[y]){ //不在同一條重鏈上的點,盡可能湊到同一條重鏈上 if(dep[top[x]]<dep[top[y]]) //在同一條重鏈上的則可以直接修改swap(x,y); //可以看下面的鏈接，關于更新講的很詳細update(tid[top[x]],tid[x],p,1,n,1); //http://blog.sina.com.cn/s/blog_7a1746820100wp67.htmlx=fa[top[x]];}if(dep[x]>dep[y])swap(x,y);update(tid[x],tid[y],p,1,n,1); } int main(){ //因為一個樹的所有重鏈覆蓋了所有的點，因此int i,x,y,z; //樹鏈剖分就是將所有重鏈分解出來，并用其它char c; //的數據結構進行維護，從而高效的實現查找和while(scanf("%d%d%d",&n,&m,&q)!=EOF){ //詢問 tim=1,edge=0;memset(son,-1,sizeof(son));memset(head,-1,sizeof(head));for(i=1;i<=n;i++)scanf("%d",&num[i]);for(i=1;i<=m;i++){scanf("%d%d",&x,&y);addedge(x,y);}dfs1(1,0,0);dfs2(1,1);build(1,n,1);while(q--){scanf(" %c",&c);if(c=='Q'){scanf("%d",&x);printf("%d\n",query(tid[x],1,n,1));}else{scanf("%d%d%d",&x,&y,&z);if(c=='D')change(x,y,-z);elsechange(x,y,z);}}}return 0; }

?

總結

以上是生活随笔為你收集整理的poj3966的全部內容，希望文章能夠幫你解決所遇到的問題。

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