1. 题目

传送门=￣ω￣=

题意：

I C1 C2 K: 把 C1 与 C2 的路径上的所有点权值加上 K

D C1 C2 K：把 C1 与 C2 的路径上的所有点权值减去 K

Q C：查询节点编号为 C 的权值

有多组数据，n<=50000

2. 题解

树链剖分模板题
树剖以后用线段树维护即可
然而智障的我老是区间加的标记不用+=而用=导致 WA

代码：

#include <bits/stdc++.h>
#define NS (50005)
#define LS(a) (a<<1)
#define RS(a) ((a<<1)|1)
using namespace std;
struct N{int l,r,d,f;N(){l=r=d=f=0;}}e[NS<<2];
int n,p,arr[NS],w[NS],fa[NS],dep[NS],siz[NS],pos[NS],top[NS],cnt;
char opt[10];
vector<int> g[NS];
void update(int a){e[a].d=e[LS(a)].d+e[RS(a)].d;}
void pdown(int a)
{
    e[LS(a)].d+=e[a].f*(e[LS(a)].r-e[LS(a)].l+1);
    e[RS(a)].d+=e[a].f*(e[RS(a)].r-e[RS(a)].l+1);
    e[LS(a)].f+=e[a].f,e[RS(a)].f+=e[a].f,e[a].f=0;
}
void build(int l,int r,int a)
{
    e[a].l=l,e[a].r=r,e[a].f=0;
    if(l==r){e[a].d=w[l];return;}
    build(l,(l+r)>>1,LS(a)),build(((l+r)>>1)+1,r,RS(a)),update(a);
}
void change(int l,int r,int k,int a)
{
    if(l<=e[a].l&&e[a].r<=r){e[a].d+=(e[a].r-e[a].l+1)*k,e[a].f+=k;return;}
    if(e[a].f)pdown(a);
    if(l<=((e[a].l+e[a].r)>>1))change(l,r,k,LS(a));
    if(r>((e[a].l+e[a].r)>>1))change(l,r,k,RS(a));
    update(a);
}
int query(int x,int a)
{
    if(e[a].l==x&&e[a].r==x)return e[a].d;
    if(e[a].f)pdown(a);
    if(x<=((e[a].l+e[a].r)>>1))return query(x,LS(a));
    return query(x,RS(a));
}
void dfs1(int u)
{
    dep[u]=dep[fa[u]]+1,siz[u]=1;
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=fa[u])fa[g[u][i]]=u,dfs1(g[u][i]),siz[u]+=siz[g[u][i]];
}
void dfs2(int u)
{
    int nxt=0,maxn=0;pos[u]=cnt++;
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=fa[u]&&siz[g[u][i]]>maxn)nxt=g[u][i],maxn=siz[g[u][i]];
    if(!nxt)return;
    top[nxt]=top[u],dfs2(nxt);
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=fa[u]&&g[u][i]!=nxt)top[g[u][i]]=g[u][i],dfs2(g[u][i]);
}
void work(int a,int b,int c)
{
    while(top[a]!=top[b])
    {
        if(dep[top[a]]>dep[top[b]])swap(a,b);
        change(pos[top[b]],pos[b],c,1),b=fa[top[b]];
    }
    if(pos[a]>pos[b])swap(a,b);
    change(pos[a],pos[b],c,1);
}
int main()
{
    while(cnt=0,~scanf("%d%d%d",&n,&p,&p))
    {
        for(int i=1;i<=n;i++)scanf("%d",&arr[i]),g[i].clear();
        for(int i=1,a,b;i<n;i++)
            scanf("%d%d",&a,&b),g[a].push_back(b),g[b].push_back(a);
        dfs1(1),top[1]=1,dfs2(1);
        for(int i=1;i<=n;i++)w[pos[i]]=arr[i];
        build(0,cnt-1,1);
        for(int i=1,a,b,c;i<=p;i++)
        {
            scanf("%s%d",opt,&a);
            if(opt[0]=='I')scanf("%d%d",&b,&c),work(a,b,c);
            else if(opt[0]=='D')scanf("%d%d",&b,&c),work(a,b,-c);
            else printf("%d\n",query(pos[a],1));
        }
    }
    return 0;
}