Description
这是一道模板题。
不保证无快读的程序能过。请务必使用快读。
给一棵有根树，这棵树由编号为1…N的N个结点组成。根结点的编号为R。每个结点都有一个权值，结点i的权值为vi。
接下来有M组操作，操作分为两类：
1 a b x，表示将「结点a到结点b的简单路径」上所有结点的权值都增加x；
2 a，表示求结点a的权值。
3 a，表示求a的子树上所有结点的权值之和。
Input
第一行有三个整数N,M和R。
第二行有N个整数，第i个整数表示vi。
在接下来的N-1行中，每行两个整数，表示一条边。
在接下来的M行中，每行一组操作。
Output
对于每组2 a操作，输出一个整数，表示结点a的权值。
Sample Input
10 15 3
4 8 -2 -4 -7 -7 -9 5 2 5
3 9
3 4
4 5
4 8
8 7
3 6
8 2
9 10
2 1
2 5
1 4 7 3
1 7 2 6
1 6 7 -7
2 1
1 10 10 -9
2 4
1 2 9 -8
2 6
1 10 5 -2
1 4 4 6
1 6 1 3
1 1 10 2
1 9 2 0
2 7
Sample Output
-7
4
-8
-14
-7
思路
- 表示
不会写正解，树剖大法好！！！
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#define int long long
#define maxn 1000005
using namespace std;
int n,m,r,val[maxn],cnt,head[maxn];
int fa[maxn],son[maxn],num[maxn],fnum[maxn],top[maxn],deep[maxn],siz[maxn];
struct fdfdfd{int flag,sum,l,r,len;}a[maxn<<2];
struct node{int next,to;}e[maxn<<1];
void addedge(int x,int y){e[++cnt].to=y; e[cnt].next=head[x]; head[x]=cnt;}
inline int read()
{
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
void dfs_1(int u,int pre)
{
fa[u]=pre; siz[u]=1; deep[u]=deep[pre]+1;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(v==pre) continue;
dfs_1(v,u); siz[u]+=siz[v];
if(son[u]==-1||siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs_2(int u,int topp)
{
top[u]=topp; num[u]=++cnt; fnum[cnt]=u;
if(son[u]!=-1) dfs_2(son[u],topp);
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(v!=fa[u]&&v!=son[u]) dfs_2(v,v);
}
}
void pushup(int x) {a[x].sum=a[x<<1].sum+a[x<<1|1].sum;}
void pushdown(int x)
{
if(a[x].flag==0) return;
a[x<<1].flag+=a[x].flag; a[x<<1].sum+=a[x].flag*a[x<<1].len;
a[x<<1|1].flag+=a[x].flag; a[x<<1|1].sum+=a[x].flag*a[x<<1|1].len;
a[x].flag=0;
}
void build(int x,int left,int right)
{
a[x].l=left; a[x].r=right; a[x].len=right-left+1;
if(left==right) {a[x].sum=val[fnum[left]]; return;}
int mid=(left+right)>>1;
build(x<<1,left,mid); build(x<<1|1,mid+1,right);
pushup(x);
}
void modify(int x,int left,int right,int d)
{
if(a[x].r<left||a[x].l>right) return;
if(left<=a[x].l&&right>=a[x].r) {a[x].flag+=d,a[x].sum+=a[x].len*d; return;}
pushdown(x);
modify(x<<1,left,right,d); modify(x<<1|1,left,right,d);
pushup(x);
}
void change_uv(int u,int v,int k)
{
while(top[u]!=top[v])
{
if(deep[top[u]]<deep[top[v]]) swap(u,v);
modify(1,num[top[u]],num[u],k);
u=fa[top[u]];
}
if(deep[u]>deep[v]) swap(u,v);
modify(1,num[u],num[v],k);
}
int query(int x,int left,int right)
{
if(a[x].r<left||a[x].l>right) return 0;
if(left<=a[x].l&&right>=a[x].r) return a[x].sum;
pushdown(x);
return query(x<<1,left,right)+query(x<<1|1,left,right);
}
signed main()
{
memset(son,-1,sizeof(son));
n=read(); m=read(); r=read();
for(int i=1;i<=n;++i) val[i]=read();
for(int i=1,u,v;i<n;++i) u=read(),v=read(),addedge(u,v),addedge(v,u);
dfs_1(r,0); cnt=0; dfs_2(r,r); build(1,1,n);
while(m--)
{
int op,a,b,x; op=read(); a=read();
if(op==1) b=read(),x=read(),change_uv(a,b,x);
else if(op==2) printf("%lld
",query(1,num[a],num[a]));
else printf("%lld
",query(1,num[a],num[a]+siz[a]-1));
}
return 0;
}