题意：
给一棵树，并给定各个点权的值，然后有3种操作：
I C1 C2 K: 把C1与C2的路径上的所有点权值加上K
D C1 C2 K：把C1与C2的路径上的所有点权值减去K
Q C：查询节点编号为C的权值
思路：
先树链剖分，然后用线段树维护一下
模板题，具体细节看代码
const int maxn = + ;
const int maxnode = maxn * ; int n, m, p;
//线段树部分
int add_value, qL, qR;
int addv[maxnode];
void update(int o, int L, int R)
{
if (qL <= L && R <= qR)
{
addv[o] += add_value;
}
else
{
int M = L + (R - L) / ;
if (qL <= M) update(lson);
if (qR > M) update(rson);
}
} void query(int o, int L, int R, LL add) {
if (qL <= L && R <= qR) {
printf("%d\n", add + addv[o]);
return;
}
int M = L + (R - L) / ;
if (qL <= M) query(lson, add + addv[o]);
if (qR > M) query(rson, add + addv[o]);
} //树链剖分部分：
//
//u为连接的点，w为边权
struct Edge { int v, w; };
vector<Edge> G[maxn]; //往往是双向边
void add_edge(int u, int v, int w)
{
G[u].push_back((Edge){v,w});
G[v].push_back((Edge){u,w});
} struct Node
{
int size, dep, son, top, fa, ti;
//依次表示第i个节点的：
//子节点数量，深度，所在链的顶端，重儿子，dfs序
} t[maxn]; int dfs_clock;//DFS时间序列 void dfs1(int u, int pa, int depth)//第一次DFS，得到size,dep,fa以及son的数据
{
t[u].son = ; //重儿子，为0表示没有重儿子
t[u].size = ; //节点数量
t[u].dep = depth;
t[u].fa = pa;
for (int i = ; i != G[u].size(); ++ i)
{
int v = G[u][i].v;
if (v == pa) continue;
dfs1(v, u, depth + );
t[u].size += t[v].size;
if (t[v].size > t[t[u].son].size) t[u].son = v;
}
} void dfs2(int u, int pa) // 得到时间戳等数据,u为当前节点，pa为父链顶端节点
{
t[u].ti = ++ dfs_clock; //u这个节点的时间戳是dfs_clock,dfs_clock下标是从1开始的，没有0！
t[u].top = pa; //top是u所在链的顶端
if (t[u].son != ) dfs2(t[u].son, t[u].top); //如果节点有重儿子，那么依旧是以pa为链顶端的一条链
for (int i = ; i != G[u].size(); ++ i)
{
int v = G[u][i].v;
if (v == t[u].son || v == t[u].fa) continue;//重儿子或者父节点，则跳过
dfs2(v, v);//新的一条链
}
} void lca(int x, int y)//更新x到y的之间所有的区间
{
while (t[x].top != t[y].top)
{
if (t[t[x].top].dep < t[t[y].top].dep) swap(x,y); //x深 y浅
qL=t[t[x].top].ti;
qR=t[x].ti;
update(,,n);
x = t[t[x].top].fa;
}
if (t[x].dep > t[y].dep) swap(x, y);//x是上面一些的节点
qL=t[x].ti;
qR=t[y].ti;
update(,,n);
} int value[maxn];
void init()
{
dfs_clock = ;
memset(addv, , sizeof(addv));
for (int i = ; i <= n; i++)
{
scanf("%d", value + i);
G[i].clear();
}
int u, v;
for (int i = ; i <= m; i++)
{
scanf("%d%d", &u, &v);
add_edge(u, v, );
}
} void solve()
{
dfs1(, , );
dfs2(, ); for (int i = ; i <= n; i++)
{
add_value = value[i];
qL = qR = t[i].ti;
update(, , n);
}
char op[];
int u, v, w;
while (p--)
{
scanf("%s", op);
if (op[] == 'Q')
{
scanf("%d", &u);
qL = qR = t[u].ti;
query(, , n, );
continue;
}
scanf("%d%d%d", &u, &v, &w);
if (op[] == 'D') w = -w;
add_value = w;
lca(u, v);
}
} int main()
{
while (scanf("%d%d%d", &n, &m, &p) == )
{
init();
solve();
}
return ;
}