题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4034
一眼链剖，但是看到操作3觉得可用LCT，但是没有链剖好写，所以写了链剖
对于操作1：单点修改，就不仔细说了，用区间修改的函数l和r相等就好
对于操作2：每个点记录下dfs时刚进入这个点时的dfs序，再记录下dfs完子树时回到这个点的，修改时区间修改就相当于修改了子树
对于操作3：链剖经典问题，不说了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 |
#include<iostream> #include<cstdio> #include<vector> #include<cstring> #include<string> #define inf 999999999 #define MAXN 100010 typedef long long ll; using namespace std; inline ll rd(){ ll x=0,y=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*y; } struct node{ ll add,sum,len; int l,r; }tree[MAXN*8]; int n,m; int w[MAXN],son[MAXN],totree[MAXN],pre[MAXN],deep[MAXN],fa[MAXN],num[MAXN],top[MAXN]; int lnum[MAXN],rnum[MAXN]; int tot=1; vector<int>v[MAXN]; void dfs1(int x,int d){ deep[x]=d; num[x]=1; for(int i=0; i<v[x].size(); i++){ int to=v[x][i]; if(to==fa[x])continue; fa[to]=x; dfs1(to,d+1); num[x]+=num[to]; if(!son[x] || num[to]>num[son[x]])son[x]=to; } } void dfs2(int x,int y){ top[x]=y; totree[x]=tot; lnum[x]=tot; pre[tot]=x; tot++; if(!son[x]){ rnum[x]=tot-1; return; } dfs2(son[x],y); for(int i=0; i<v[x].size(); i++){ int to=v[x][i]; if(to!=son[x] && to!=fa[x])dfs2(to,to); } rnum[x]=tot-1; } void build(int x,int l,int r){ tree[x].l=l; tree[x].r=r; tree[x].len=r-l+1; if(l==r){ tree[x].sum=(ll)w[pre[l]]; return; } int mid=(l+r)/2; build(x*2,l,mid); build(x*2+1,mid+1,r); tree[x].sum=tree[x*2].sum+tree[x*2+1].sum; } void pushdown(int x){ int ls=x*2,rs=x*2+1; if(tree[x].add){ tree[ls].sum+=tree[x].add*tree[ls].len; tree[rs].sum+=tree[x].add*tree[rs].len; tree[ls].add+=tree[x].add; tree[rs].add+=tree[x].add; tree[x].add=0; } } void update(int x,int l,int r,ll z){ if(tree[x].l==l && tree[x].r==r){ tree[x].sum+=z*tree[x].len; tree[x].add+=z; return; } pushdown(x); int mid=(tree[x].l+tree[x].r)/2; if(r<=mid)update(x*2,l,r,z); else if(l>mid) update(x*2+1,l,r,z); else update(x*2,l,mid,z),update(x*2+1,mid+1,r,z); tree[x].sum=tree[x*2].sum+tree[x*2+1].sum; } ll query_sum(int x,int l,int r){ if(tree[x].l>=l && tree[x].r<=r)return tree[x].sum; pushdown(x); int mid=(tree[x].l+tree[x].r)/2; if(r<=mid)return query_sum(x*2,l,r); else if(l>mid)return query_sum(x*2+1,l,r); else return query_sum(x*2,l,mid)+query_sum(x*2+1,mid+1,r); } ll find_sum(int x){ int t1=top[x]; ll ans=0; while(x){ pushdown(x); ans+=query_sum(1,totree[t1],totree[x]); x=fa[t1]; t1=top[x]; } return ans; } int main(){ n=rd(),m=rd(); for(int i=1; i<=n; i++)w[i]=rd(); for(int i=1; i<n; i++){ int x=rd(),y=rd(); v[x].push_back(y); v[y].push_back(x); } dfs1(1,1); dfs2(1,1); build(1,1,n); while(m--){ int op=rd(),x; ll y; if(op==1){ x=rd(),y=rd(); update(1,totree[x],totree[x],y),w[x]+=y; } else if(op==2){ x=rd(),y=rd(); update(1,lnum[x],rnum[x],y); } else{ x=rd(); printf("%lld\n",find_sum(x)); } } return 0; } |
