4034: [HAOI2015]T2

Description

?有一棵點數為 N 的樹，以點 1 為根，且樹點有邊權。然后有 M 個

操作，分為三種： 操作 1 ：把某個節點 x 的點權增加 a 。 操作 2 ：把某個節點 x 為根的子樹中所有點的點權都增加 a 。 操作 3 ：詢問某個節點 x 到根的路徑中所有點的點權和。

Input

?第一行包含兩個整數 N, M 。表示點數和操作數。

接下來一行 N 個整數，表示樹中節點的初始權值。 接下來 N-1 行每行三個正整數 fr, to ， 表示該樹中存在一條邊 (fr, to) 。 再接下來 M 行，每行分別表示一次操作。其中第一個數表示該操 作的種類（ 1-3 ） ，之后接這個操作的參數（ x 或者 x a ） 。

Output

?對于每個詢問操作，輸出該詢問的答案。答案之間用換行隔開。

Sample Input

5 5
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3

Sample Output

6
9
13

HINT

?

?對于 100% 的數據， N,M<=100000 ，且所有輸入數據的絕對值都不

會超過 10^6 。

?

Source

?

題解：

裸題了，

代碼來自HZWER

#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 #define mod 1000000000 using namespace std; int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } int n,m,cnt; int last[100005]; int id,pos[100005],mx[100005],v[100005]; int bl[100005],size[100005],fa[100005]; ll tag[400005],sum[400005]; struct edge{int to,next; }e[200005]; void insert(int u,int v) {e[++cnt]=(edge){v,last[u]};last[u]=cnt;e[++cnt]=(edge){u,last[v]};last[v]=cnt; } void dfs(int x) {size[x]=1;for(int i=last[x];i;i=e[i].next)if(e[i].to!=fa[x]){fa[e[i].to]=x;dfs(e[i].to);size[x]+=size[e[i].to];} } void dfs2(int x,int cha) {bl[x]=cha;pos[x]=mx[x]=++id;int k=0;for(int i=last[x];i;i=e[i].next)if(e[i].to!=fa[x]&&size[e[i].to]>size[k])k=e[i].to;if(k){dfs2(k,cha);mx[x]=max(mx[x],mx[k]);}for(int i=last[x];i;i=e[i].next)if(e[i].to!=fa[x]&&e[i].to!=k){dfs2(e[i].to,e[i].to);mx[x]=max(mx[x],mx[e[i].to]);} } void pushdown(int l,int r,int k) {if(l==r)return;int mid=(l+r)>>1;ll t=tag[k];tag[k]=0;tag[k<<1]+=t;tag[k<<1|1]+=t;sum[k<<1]+=t*(mid-l+1);sum[k<<1|1]+=t*(r-mid); } void add(int k,int l,int r,int x,int y,ll val) {if(tag[k])pushdown(l,r,k);if(l==x&&y==r){tag[k]+=val;sum[k]+=(r-l+1)*val;return;}int mid=(l+r)>>1;if(x<=mid)add(k<<1,l,mid,x,min(mid,y),val);if(y>=mid+1)add(k<<1|1,mid+1,r,max(mid+1,x),y,val);sum[k]=sum[k<<1]+sum[k<<1|1]; } ll query(int k,int l,int r,int x,int y) {if(tag[k])pushdown(l,r,k);if(l==x&&y==r)return sum[k];int mid=(l+r)>>1;ll ans=0;if(x<=mid)ans+=query(k<<1,l,mid,x,min(mid,y));if(y>=mid+1)ans+=query(k<<1|1,mid+1,r,max(mid+1,x),y);return ans; } ll query(int x) {ll ans=0;while(bl[x]!=1){ans+=query(1,1,n,pos[bl[x]],pos[x]);x=fa[bl[x]];}ans+=query(1,1,n,1,pos[x]);return ans; } int main() {n=read();m=read();for(int i=1;i<=n;i++)v[i]=read();for(int i=1;i<n;i++){int u=read(),v=read();insert(u,v);}dfs(1);dfs2(1,1);for(int i=1;i<=n;i++)add(1,1,n,pos[i],pos[i],v[i]);int opt,x,a;while(m--){opt=read();x=read();if(opt==1){a=read();add(1,1,n,pos[x],pos[x],a);}if(opt==2){a=read();add(1,1,n,pos[x],mx[x],a);}if(opt==3)printf("%lld\n",query(x));}return 0; }

?

轉載于:https://www.cnblogs.com/zxhl/p/5267187.html

總結

以上是生活随笔為你收集整理的BZOJ 4034: [HAOI2015]T2 树链剖分的全部內容，希望文章能夠幫你解決所遇到的問題。

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