一、写在前面
终于开始开坑link-cut-tree这个了，对于网上找到的大佬的前进路线，进行了一番研发，发现实际上可以实现对于树链拋分的制作。经历了若干长时间之后终于打了出来（为什么每次学什么东西都会强行写3遍左右。。。）
二、题意
阿拉贡同学发现一棵树装的若干营地有了若干敌人（可以是负数），这些敌人的变化情况会使用类似于“A-B之间的路上的所有营地都增加某个数量的人数”来进行。最后任意时间有询问：某个点当前有多少人？
三、题解
树链拋分的思路是这样的：首先把一棵树，对于每个节点都将会有：将子节点数量最多的一条链称为重链，其他各子节点各自组成以他们开头的重链。最终会使得一颗树的形状确定之后，就会唯一确定一个树链拋分方案（可能会在相同子节点的处理上有些分歧）。之后对于路径的寻找，会发现实际上，可以方便的找到任意一条路径，时间复杂度低于logN
对于任意树链拋分代码需要以下几个数组：
child代表某个节点为根节点的子节点的个数
deep代表当前节点的深度
number代表适用树链拋分的方式进行重新编号之后的映射
fa代表父节点编号
top当前重链的开头元素编号
#include<bits/stdc++.h>
using namespace std; #define veci vector<int>
#define ll long long
const long long MAXN=5e4+; int arr[MAXN],child[MAXN],top[MAXN],deep[MAXN],tree[MAXN],fa[MAXN];
veci G[MAXN];
int number[MAXN];
int n,m,p,size=; void insert(int pos,int key)
{
while(pos<MAXN)
{
tree[pos]+=key;
pos+=pos&(-pos);
}
// cout<<pos<<endl;
} ll getSum(int pos)
{
ll ans=;
while(pos)
{
ans+=tree[pos];
pos-=pos&(-pos);
}
// cout<<"checkSum: "<<ans<<ends<<pos<<endl;
return ans;
} void dfs_1(int now,int last,int dep)
{
int len=G[now].size();
fa[now]=last;
deep[now]=dep;
child[now]=;
for(int i=;i<len;++i)
{
int tar=G[now][i];
if(tar==last)continue;
dfs_1(tar,now,dep+);
child[now]+=child[tar];
}
} void dfs(int now,int last,int first)
{
top[now]= first? first:now;
// if(top[now]==now)
// {
// cout<<now<<" checked "<<endl;
// }
int len=G[now].size();
// cout<<now<<"checkNum: "<<size<<endl;
number[now]=size++; int maxx=-;int pos=-;
for(int i=;i<len;++i)
{
int tar=G[now][i];
if(tar==last)continue;
if(maxx<child[tar])
{
maxx=child[tar];
pos=i;
}
}
if(pos!=-)dfs(G[now][pos],now,top[now]);
for(int i=;i<len;++i)
{
int tar=G[now][i];
if(i==pos||tar==last)continue;
dfs(tar,now,);
}
}
void update(int a,int b,int key)
{
// cout<<"checkUP"<<a<<ends<<b<<ends<<key<<endl;
int t1=top[a];
int t2=top[b];
//
while(t1!=t2)
{ if(deep[t1]<deep[t2])
{
swap(t1,t2);
swap(a,b);
}
insert(number[t1],key);
insert(number[a]+,-key);
// cout<<"checkTop: "<<t1<<ends<<a<<endl;
a=fa[t1];
// b=fa[t2];
t1=top[a];
// t2=top[b];
}
int star=min(number[a],number[b]);
int endd=max(number[a],number[b])+;
// cout<<"check_line: "<<star<<ends<<endd<<endl;
insert(star,key);
insert(endd,-key);
} int query(int a)
{
int pos=number[a];
return getSum(pos)+arr[a];
} void init()
{
size=;
for(int i=;i<=n;++i)
{
G[i].clear();
scanf("%d",&arr[i]);
}
memset(tree,,*(n+));
for(int i=;i<n;++i)
{
int a,b;
scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}dfs_1(,,);
dfs(,,);
for(int i=;i<p;++i)
{
char c[];
scanf("%s",c);
if(c[]=='I')
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
update(a,b,c); }else if(c[]=='D')
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
update(a,b,-c);
}else if(c[]=='Q')
{
int a;
scanf("%d",&a);
cout<<query(a)<<"\n";
}
}
} int main()
{
// cin.sync_with_stdio(false);
while(scanf("%d%d%d",&n,&m,&p)!=EOF)init(); return ;
}