#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;

namespace dts
{
    typedef long long ll;
    ll cnt,maxdep;
    class tr_node
    {
        public:
            ll fa,dep,size,hs,top,id;
            vector<ll> s;
    };
    ll rk[(1<<15)+1];
    tr_node tr[(1<<15)+1];
    void tr_dfs1(ll now,ll fa)
    {
        tr[now].fa=fa;
        tr[now].dep=tr[tr[now].fa].dep+1;
        maxdep=max(maxdep,tr[now].dep);
        tr[now].size=1;
        tr[now].hs=-1;
        for (ll i=0;i<tr[now].s.size();i++)
        {
            ll next=tr[now].s[i];
            tr_dfs1(next,now);
            tr[now].size+=tr[next].size;
            if (tr[now].hs==-1)
                tr[now].hs=next;
            else if (tr[tr[now].hs].size<tr[next].size)
                tr[now].hs=next;
        }
    }
    void tr_dfs2(ll now,ll top)
    {
        tr[now].top=top;
        tr[now].id=++cnt;
        rk[cnt]=now;
        if (tr[now].hs!=-1)
        {
            tr_dfs2(tr[now].hs,top);
            for (ll i=0;i<tr[now].s.size();i++)
                if (tr[now].s[i]!=tr[now].hs)
                    tr_dfs2(tr[now].s[i],tr[now].s[i]);
        }
    }
    void tr_build(ll Mrw)
    {
        cnt=maxdep=0;
        tr_dfs1(Mrw,Mrw);
        tr_dfs2(Mrw,Mrw);
    }
    ll lca(ll x,ll y)
    {
        while (tr[x].top!=tr[y].top)
        {
            if (tr[tr[x].top].dep<tr[tr[y].top].dep)
                swap(x,y);
            x=tr[tr[x].top].fa;
        }
        if (tr[x].dep<tr[y].dep)
            return x;
        else
            return y;
    }
    
    class st_node
    {
        public:
            ll l,r,mid;
            ll sum=0,sumlz=0;
            ll len()
            {
                return r-l+1;
            }
    };
    st_node nst[(1<<17)+1],lst[(1<<17)+1];//nst:按節點的線段樹，lst:按深度的線段樹
    #define lc(now) ((now)<<1)
    #define rc(now) ((now)<<1|1)
    void st_update(st_node *st,ll now,ll l,ll r,ll val);
    void st_pushdown(st_node *st,ll now)
    {
        if (st[now].sumlz!=0)
        {
            st_update(st,lc(now),st[now].l,st[now].mid,st[now].sumlz);
            st_update(st,rc(now),st[now].mid+1,st[now].r,st[now].sumlz);
            st[now].sumlz=0;
        }
    }
    void st_update(st_node *st,ll now,ll l,ll r,ll val)
    {
        if (st[now].l==l&&r==st[now].r)
        {
            st[now].sum+=st[now].len()*val;
            st[now].sumlz+=val;
        }
        else
        {
            st_pushdown(st,now);
            if (r<=st[now].mid)
                st_update(st,lc(now),l,r,val);
            else if (st[now].mid+1<=l)
                st_update(st,rc(now),l,r,val);
            else
                st_update(st,lc(now),l,st[now].mid,val),st_update(st,rc(now),st[now].mid+1,r,val);
            st[now].sum=st[lc(now)].sum+st[rc(now)].sum;
        }
    }
    ll st_ask(st_node *st,ll now,ll l,ll r)
    {
        if (st[now].l==l&&r==st[now].r)
            return st[now].sum;
        else
        {
            st_pushdown(st,now);
            if (r<=st[now].mid)
                return st_ask(st,lc(now),l,r);
            else if (st[now].mid+1<=l)
                return st_ask(st,rc(now),l,r);
            else
                return st_ask(st,lc(now),l,st[now].mid)+st_ask(st,rc(now),st[now].mid+1,r);
        }
    }
    void st_build(st_node *st,ll now,ll l,ll r,ll *data)
    {
        st[now].l=l,st[now].r=r;
        st[now].sumlz=0;
        if (l<r)
        {
            st[now].mid=(l+r)>>1;
            st_build(st,lc(now),l,st[now].mid,data);
            st_build(st,rc(now),st[now].mid+1,r,data);
            st[now].sum=st[lc(now)].sum+st[rc(now)].sum;
        }
        else
            st[now].sum=data[l];
    }
    
    ll ask(ll x,ll y)
    {
        ll lcan=lca(x,y),i,j,ians=0,jans=0;
        for (i=x;tr[i].top!=tr[lcan].top;i=tr[tr[i].top].fa)
            ians+=st_ask(&nst[-1],1,tr[tr[i].top].id,tr[i].id);
        for (j=y;tr[j].top!=tr[lcan].top;j=tr[tr[j].top].fa)
            jans+=st_ask(&nst[-1],1,tr[tr[j].top].id,tr[j].id);
        ll ansn=ians+jans+st_ask(&nst[-1],1,tr[lcan].id,tr[i].id)+st_ask(&nst[-1],1,tr[lcan].id,tr[j].id)-st_ask(&nst[-1],1,tr[lcan].id,tr[lcan].id);
        ll ansl=st_ask(&lst[-1],1,tr[lcan].dep,tr[x].dep)+st_ask(&lst[-1],1,tr[lcan].dep,tr[y].dep)-st_ask(&lst[-1],1,tr[lcan].dep,tr[lcan].dep);
        return ansn+ansl;
    }
    
    ll n,q,Mrw,a[(1<<15)+1],d[(1<<15)+1];
    
    void main()
    {
        scanf("%lld%lld",&n,&q);
        for (ll i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        for (ll i=1;i<=n;i++)
            tr[i].s.clear();
        for (ll i=1;i<=n;i++)
        {
            ll fa;
            scanf("%lld\n",&fa);
            if (fa!=-1)
                tr[fa].s.push_back(i);
            else
                Mrw=i;
        }
        tr_build(Mrw);
        for (ll i=1;i<=n;i++)
            if (tr[rk[i]].dep&1)
                d[i]=a[rk[i]];
            else
                d[i]=-a[rk[i]];
        st_build(&nst[-1],1,1,cnt,&d[0]);
        memset(d,0,sizeof(d));
        st_build(&lst[-1],1,1,maxdep,&d[0]);
        for (ll i=1;i<=q;i++)
        {
            char o;
            ll x,y;
            scanf("%c%lld%lld\n",&o,&x,&y);
            if (o=='A')
                printf("%lld\n",llabs(ask(x,y)));
            else if (o=='M')
            {
                if (x&1)
                    st_update(&lst[-1],1,x,x,y);
                else
                    st_update(&lst[-1],1,x,x,-y);
            }
        }
    }
}

int main()
{
    dts::main();
}

树链剖分+线段树+树状数组==AC

#pragma GCC optimize("O3")
#define _USE_MATH_DEFINES
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cctype>
#include <sstream>
#include <cfloat>
#include <complex>
#include <climits>
#include <new>
#include <memory>
#include <cerrno>
#include <cassert>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <bitset>
#include <utility>
#include <iterator>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <algorithm>
#include <functional>
#include <random>
#include <regex>
#define fir first
#define sec second
#define lson x<<1
#define rson x<<1|1
#define npos string::npos
#define FF fflush(stdout)
#define sqr(X) (X)*(X)
#define LB(X) (X)&(-(X))
#define MP(X,Y) make_pair((X),(Y))
#define ALL(X) (X).begin(),(X).end()
#define INS(X) inserter((X),(X).begin())
#define MEM(X,Y) memset((X),(Y),sizeof((X)))
#define EPS 1e-7
using namespace std;
typedef long long LL;
typedef long double LD;
typedef vector<int> VI;
typedef complex<int> CI;
typedef unsigned int UI;
typedef pair<LL,LL> PLL;
typedef map<int,int> MII;
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
typedef complex<double> CD;
typedef map<string,int> MSI;
typedef unsigned long long ULL;
typedef priority_queue<int> PQ;
typedef pair<double,double> PDD;
const LL MOD = 1000000007;
const int M = 5000005;
const int N = 20005;
int dep[N],n,m,fa[N],rot,son[N],sz[N],tot,top[N],id[N],rk[N],a[N],t1,t2;
char ch;
LL c[N];
struct u
{
    int l,r,v;
    int mid() {return (l+r)>>1;}
}e[N<<2];

VI g[N];

void dfs(int x,int y)
{
    dep[x]=dep[y]+1;
    sz[x]=1;
    for (auto &i : g[x])
    if (i!=y)
    {
        dfs(i,x);
        sz[x]+=sz[i];
        if (sz[i]>sz[son[x]]) son[x]=i;
    }
}

void dfs2(int x,int y)
{
    top[x]=y;
    id[x]=++tot;
    rk[tot]=x;
    if (son[x]) dfs2(son[x],y);
    for (auto &i : g[x])
    if (i!=fa[x] && i!=son[x]) dfs2(i,i);
}

void add(int x,int y)
{
    if (x<=0) return ;
    while (x<=n)
    {
        c[x]+=y;
        x+=LB(x);
    }
}

LL all(int x)
{
    LL res=0;
    while (x>0) 
    {
        res+=c[x];
        x-=LB(x);
    }
    return res;
}

void pu(int x)
{
    e[x].v=e[lson].v+e[rson].v;
}

void build(int l,int r,int x)
{
    e[x].l=l;
    e[x].r=r;
    if (l==r) 
    {
        e[x].v=dep[rk[l]]&1 ? a[rk[l]] : (-a[rk[l]]);
        return ;
    }
    int m=e[x].mid();
    build(l,m,lson);
    build(m+1,r,rson);
    pu(x);
}

LL que(int l,int r,int x)
{
    if (l==e[x].l && r==e[x].r) return e[x].v;
    int m=e[x].mid();
    if (r<=m) return que(l,r,lson);
    else if (l>m) return que(l,r,rson);
    else return que(l,m,lson)+que(m+1,r,rson);
}

LL hunt(int l,int r)
{
    LL res=0;
    while (top[l]!=top[r])
    {
        if (dep[top[l]]<dep[top[r]]) swap(l,r);
        res+=que(id[top[l]],id[l],1);
        res+=all(dep[l])-all(dep[top[l]]-1);
        l=fa[top[l]];
    }
    if (dep[l]>dep[r]) swap(l,r);
    res+=que(id[l],id[r],1);
    res+=all(dep[r])-all(dep[l]-1);
    return abs(res);
}

int main()
{
    MEM(c,0);
    MEM(son,0);
    MEM(dep,0);
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++) 
    {
        scanf("%d",&fa[i]);
        if (fa[i]>0) g[fa[i]].push_back(i);
        else rot=i;
    }
    tot=0;
    dfs(rot,0);
    dfs2(rot,rot);
    build(1,n,1);
    while (m--)
    {
        ch=getchar();
        while (!isalpha(ch)) ch=getchar();
        scanf("%d %d",&t1,&t2);
        if (ch=='M') add(t1,t1&1 ? t2 : (-t2));
        else printf("%lld\n",hunt(t1,t2));
    }
    return 0;
}

May the father of understanding guide U.

好题啊，把我这些天学的都包括进去了

#Algorithm:
1)DFS理顺整棵树，记录节点i的深度depth[i] 和 父亲f[i][0]，记录从根节点到节点i这条路上的工资之和sum[i]（由于要找奇数层和偶数层工资总数之差，把奇数层工资存成正数，偶数层存成负数即可）
2)倍增预处理f[i][j]表示i的第2^j个祖先
3)对于每个修改，用树状数组tree[i]维护层上增量的前缀和
4)对于每个询问,求k=LCA(x, y),显然按照楼下__wzc1995__大大：sum[x]+sum[y]-2*sum[k]+pay[k]+query(teee[x])-query(tree[k]-1)+query(tree[y])-query(tree[k]) 再取绝对值 ORZ

#Code(C++):

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define maxn 20000+100
#define LL long long
LL tree[maxn];
LL depth[maxn], sum[maxn], pay[maxn];
LL list[maxn][20], f[maxn][20];
LL deep, n, m, boss;

LL lowbit(LL x)
{
return -x & x;
}

LL getsum(LL x)
{
if(x<1)return 0;
LL sum = 0;
for(LL i = x; i; i -= lowbit(i))
sum += tree[i];
return sum;
}

void update(LL x, LL val)
{
for(LL i = x; i <= deep; i += lowbit(i))
tree[i] += val;
} // BIT

bool odd(LL x)
{
return x & 1;
}

void dfs(LL pos, LL dep, LL last)
{
if(dep > deep) deep = dep;
depth[pos] = dep;
f[pos][0] = last;
sum[pos] = sum[last];
if(!odd(dep)) pay[pos] = -pay[pos];
sum[pos] += pay[pos];

for(LL i = 1; i <= list[pos][0]; i++)
dfs(list[pos][i], dep + 1, pos);
} // DFS

void ready()
{
for(LL j = 1; j <= log2(n); j++)
for(LL i = 1; i <= n; i++)
f[i][j] = f[f[i][j-1]][j-1];
}

void pushup(LL &x, LL pos)
{
while(depth[x] > depth[pos])
{
LL k = (LL) log2(depth[x] - depth[pos]);
x = f[x][k];
}
}

LL LCA(LL a, LL b)
{
if(depth[a] > depth[b])pushup(a, b);
else pushup(b, a);
if(a == b)return a;
LL s = (int) log2(n);
while(f[a][0] != f[b][0])
{
while(f[a][s] == f[b][s])s--;
a = f[a][s];
b = f[b][s];
}
return f[a][0];
} // Prefix Doubling LCA

int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);

scanf("%d%d", &n, &m);
for(LL i = 1; i <= n; i++)
scanf("%d", &pay[i]);
for(LL i = 1; i <= n; i++)
{
int x;
scanf("%d", &x);
if(x == -1)
boss = i;
else
{
list[x][++list[x][0]] = i;
}
}
dfs(boss, 1, 0);

/*for(int i=1;i<=n;i++){
cout<<pay[i]<<" "<<sum[i]<<" "<<depth[i]<<" "<<list[i][0]<<endl;
}*/
//cout<<(1&1)<<" "<<(10&1)<<endl;

ready();

/*for(int i=1;i<=n;i++)
{
for(int j=0; j<=log2(n);j++)
cout<<f[i][j]<<" ";
cout<<endl;
}*/

for(LL i = 1; i <= m; i++)
{
getchar();
char op;
int a, b;
scanf("%c %d %d", &op, &a, &b);
if(op == 'M')
{
if(odd(a))
update(a, b);
else
update(a, -b);
}
else
{
LL lca = LCA(a, b);
printf("%lld\n", abs( sum[a] + sum[b] - 2 * sum[lca] + pay[lca]
+ getsum(depth[a]) + getsum(depth[b]) - getsum(depth[lca]) - getsum(depth[lca] - 1) ));
}
}

//system("pause");
return 0;
}

#评测结果

编译成功

foo.cpp: In function 'int main()':
foo.cpp:87:25: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat]
foo.cpp:87:25: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat]
foo.cpp:89:28: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat]
foo.cpp:134:116: warning: unknown conversion type character 'l' in format [-Wformat]
foo.cpp:134:116: warning: too many arguments for format [-Wformat-extra-args]

测试数据 #0: Accepted, time = 0 ms, mem = 7368 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 7364 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 7376 KiB, score = 10

测试数据 #3: Accepted, time = 15 ms, mem = 7440 KiB, score = 10

测试数据 #4: Accepted, time = 234 ms, mem = 8928 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 7364 KiB, score = 10

测试数据 #6: Accepted, time = 31 ms, mem = 7368 KiB, score = 10

测试数据 #7: Accepted, time = 140 ms, mem = 7376 KiB, score = 10

测试数据 #8: Accepted, time = 78 ms, mem = 7380 KiB, score = 10

测试数据 #9: Accepted, time = 156 ms, mem = 7380 KiB, score = 10

Accepted, time = 654 ms, mem = 8928 KiB, score = 100

原先T的三组是被机房吴犇嘴巴A掉 ，蔡犇秒掉的。
树剖+flag数组记录层的改变量，最后暴力出奇迹，妙不可言
build里面把偶数层掷成负数，奇数层不变；询问时若问的是偶数层，就把添加的值变成负数，然后就可以顺理成章地进行区间求和了，将求出来的和取个绝对值就是答案。添加的flag数组可以避开单点修改，将速度提高许多。
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 3620 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 3624 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 3620 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 3640 KiB, score = 10
测试数据 #4: Accepted, time = 234 ms, mem = 4236 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 3620 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 3624 KiB, score = 10
测试数据 #7: Accepted, time = 93 ms, mem = 3620 KiB, score = 10
测试数据 #8: Accepted, time = 62 ms, mem = 3620 KiB, score = 10
测试数据 #9: Accepted, time = 125 ms, mem = 3620 KiB, score = 10
Accepted, time = 544 ms, mem = 4236 KiB, score = 100
代码
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <cctype>
#include <ctime>
#define INF (1<<29)
#define N 21000
using namespace std;

void read(int &k)
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
k=x*f;
}

int n,Q,nn,inde,root;
int fa[N],p[N],size[N],top[N],tree[N],deep[N],son[N],a[N],numdeep[N],ftree[N],flag[N];

struct edge
{
int a,b,nt;
}e[100001];

struct segtree
{
int l,r,val;
}seg[N*4];

void anode(int x,int y)
{
nn++;e[nn].a=x;e[nn].b=y;e[nn].nt=p[x];p[x]=nn;
nn++;e[nn].a=y;e[nn].b=x;e[nn].nt=p[y];p[y]=nn;
}

void dfs1(int x)
{
size[x]=1;
for(int i=p[x];i;i=e[i].nt)
{
int v=e[i].b;
if(v==fa[x]) continue;
deep[v]=deep[x]+1;
fa[v]=x;
dfs1(v);
size[x]+=size[v];
if(size[v]>size[son[x]])
son[x]=v;
}
}

void dfs2(int x,int chain)
{
top[x]=chain,tree[x]=++inde;
ftree[tree[x]]=x;
if(!son[x]) return ;
dfs2(son[x],chain);
for(int i=p[x];i;i=e[i].nt)
{
int v=e[i].b;
if(v!=fa[x]&&v!=son[x])
dfs2(v,v);
}
}

void pushup(int k)
{
seg[k].val=seg[k<<1].val+seg[k<<1|1].val;
}

void build(int k,int l,int r)
{
seg[k].l=l,seg[k].r=r;
int mid=(l+r)/2;
if(l==r)
{
if(deep[ftree[l]]%2==1)
seg[k].val=a[ftree[l]];
else
seg[k].val=-a[ftree[l]];
return ;
}

build(k<<1,l,mid),build(k<<1|1,mid+1,r);
pushup(k);
}

void update(int k,int pos,int val)
{
int mid=(seg[k].l+seg[k].r)/2;
if(seg[k].l==pos&&seg[k].r==pos)
{
seg[k].val+=val;
return ;
}
if(pos<=mid) update(k<<1,pos,val);
else update(k<<1|1,pos,val);
pushup(k);
}

int query(int k,int l,int r)
{
int mid=(seg[k].l+seg[k].r)/2;
if(seg[k].l==l&&seg[k].r==r)
return seg[k].val;
if(r<=mid) return query(k<<1,l,r);
else if(l>mid) return query(k<<1|1,l,r);
else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
}

int solvequery(int x,int y)
{
int rnt=0;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
rnt+=query(1,tree[top[x]],tree[x]);
for(int i=deep[top[x]];i<=deep[x];i++)
rnt+=flag[i];
x=fa[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
rnt+=query(1,tree[x],tree[y]);
for(int i=deep[x];i<=deep[y];i++)
rnt+=flag[i];
return rnt;
}

int main()
{
//freopen("D:\code\in.txt","r",stdin);
read(n),read(Q);
for(int i=1;i<=n;i++)
read(a[i]);
for(int x,i=1;i<=n;i++)
{
read(x);
if(x==-1)
{
root=i;
continue;
}
anode(i,x);
}
deep[root]=1;fa[root]=-1;
dfs1(root),dfs2(root,root);
for(int i=1;i<=n;i++)
numdeep[deep[i]]++;
build(1,1,n);
while(Q--)
{
char s[2];
int x,y;
scanf("%s",s);
read(x),read(y);
if(s[0]=='M')
{
if(x%2==0) y=-y;
flag[x]+=y;
}
else
printf("%d\n",abs(solvequery(x,y)));
}
return 0;
}

lca+树状数组
测试数据 #0: Accepted, time = 0 ms, mem = 2872 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 2872 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 2872 KiB, score = 10
测试数据 #3: Accepted, time = 31 ms, mem = 2880 KiB, score = 10
测试数据 #4: Accepted, time = 234 ms, mem = 3252 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 2868 KiB, score = 10
测试数据 #6: Accepted, time = 19 ms, mem = 2868 KiB, score = 10
测试数据 #7: Accepted, time = 234 ms, mem = 2872 KiB, score = 10
测试数据 #8: Accepted, time = 125 ms, mem = 2868 KiB, score = 10
测试数据 #9: Accepted, time = 136 ms, mem = 2868 KiB, score = 10
Accepted, time = 779 ms, mem = 3252 KiB, score = 100

比赛的时候将级别和序列号弄混了，原本A的程序啊，狂晕

先用倍增求出LCA。。

设两点为x,y，LCA=z，d[i]表示深度，sum[i]表示i点到根节点的初始工资和是多少，奇数层就是正的，偶数层就是负的，加一起。再用一个树状数组维护每层工资的加减情况，同样是奇数的加上t，偶数的减去t。

询问的时候输出sum[x]+sum[y]-2*sum[z]+((d[z]&1)?a[z]:-a[z])+query(d[x])-query(d[z]-1)+query(d[y])-query(d[z])再取绝对值即可。。

更新的时候

if(x&1) updata(x,t);

else updata(x,-t);

我来说说我的坑爹做法……

首先bfs一下，得出每个节点的层级level[i]。

然后维护两棵Link-Cut-Tree,一棵维护偶数层的，一棵维护奇数层的。

用两个树状数组，分别维护奇数和偶数层的额外修改的工资。

修改操作：在树状数组里面修改

查询操作，首先在两棵LCT里面分别查出路径和，假设LCA(a,b)=x，那么x->a和x->b路径上分别存在等级为level[x]~level[a],level[x]~level[.b] 的员工各一名。然后在树状数组里面查询修改值，一起计算即可。

做法很坑爹，不过n，q达到数十万级别也能轻松过掉。

水。。。。。。//#include<cstdio>

#include<algorithm>

#define rp 200000

#include<cstring>

#include<cmath>

using namespace std;
int n, q, root, price[rp];
int h[rp], to[rp], nex[rp], p = 0;
int deep[rp], maxlen = 0, work[rp];
int H[rp], To[rp], Nex[rp], P = 0;
int shu = 0, l[rp], f[30000][21];
int st[rp];
struct sss {
int rt;
int w;
}dp[rp];
struct ssss {
int sum;
int val;
}tree[rp*5];
char str[10];
void Build(int a, int b) {
To[++P] = b;
Nex[P] = H[a];
H[a] = P;
}

void dfs(int u, int fa) {
f[u][0] = fa;
deep[u] = deep[fa] + 1;
if(deep[u] & 1) price[u] = price[fa] + work[u];
else price[u] = price[fa] - work[u];
Build(deep[u], u);
maxlen = max(maxlen, deep[u]);
for(int i = h[u]; i != 0; i = nex[i]) {
int v = to[i];
if(v == fa) continue;
dfs(v, u);
}
}

void build(int a, int b) {
to[++p] = b;
nex[p] = h[a];
h[a] = p;
}

void renewfather(int rt) {
tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
return ;
}

void renewchild(int rt, int L, int r) {
int val = tree[rt].val, z = rt<<1, y = rt<<1|1, mid = (L + r) >> 1;
tree[z].val += val;
tree[y].val += val;
tree[z].sum += (L - mid + 1)*val;
tree[y].sum += (r - mid)*val;
tree[rt].val = 0;
return ;
}

void bbuild(int rt, int L, int r) {
tree[rt].val = 0;
if(L == r) {
tree[rt].sum = dp[L].w;
return ;
}

int mid = (L + r) >> 1;
bbuild(rt<<1, L, mid);
bbuild(rt<<1|1, mid + 1, r);
renewfather(rt);
}

int find(int rt, int L, int r, int x) {
if(L == r && x == L) return tree[rt].sum;
if(tree[rt].val != 0) renewchild(rt, L, r);
int mid = (L + r) >> 1;
if(x <= mid) return find(rt<<1, L, mid, x);
else return find(rt<<1|1, mid + 1, r, x);
}

void add(int rt, int z, int y, int L, int R, int val) {
if(L <= z && y <= R) {
tree[rt].val += val;
tree[rt].sum += (y - z + 1)*val;
return ;
}
if(tree[rt].val != 0) renewchild(rt, z, y);
int mid = (z + y) >> 1;
if(L <= mid) add(rt<<1, z, mid, L, R, val);
if(R > mid) add(rt<<1|1, mid + 1, y, L, R, val);
renewfather(rt);

}

void init() {
for(int j = 0; (1<<j) <= n; j++)
for(int i = 1; i <= n; i++)
if(f[i][j - 1] != 0)
f[i][j] = f[f[i][j - 1]][j - 1];
}

int lca(int a, int b) {
if(a == b) return a;
if(deep[a] < deep[b]) swap(a, b);
int i, j;
for(i = 0; (1<<i) <= deep[a]; i++) ;
i--;
for(j = i; j >= 0; j--)
if(deep[a] - (1<<j) >= deep[b])
a = f[a][j];
if(a == b) return a;
for(j = i; j >= 0; j--)
if(f[a][j] != 0 && f[a][j] != f[b][j]) {
a = f[a][j];
b = f[b][j];

}
return f[a][0];

}

int main() {
memset(tree, 0, sizeof(tree));
scanf("%d %d", &n, &q);
for(int i = 1; i <= n; i++)
scanf("%d", &work[i]);
for(int i = 1; i <= n; i++) {
int laoban;
scanf("%d", &laoban);
if(laoban != -1) {
build(laoban, i);
build(i, laoban);
}
else root = i;
}
dfs(root, 0);
for(int i = 1; i <= maxlen; i++) {
l[i] = shu+1;
for(int j = H[i]; j != 0; j = Nex[j]) {
int v = To[j];
dp[++shu].rt = v;
st[v] = shu;
}
}
for(int i = 1; i <= n; i++)
dp[i].w = price[dp[i].rt];
bbuild(1, 1, n);
init();
for(int i = 1; i <= q; i++) {
int lv, t, x, y;
scanf("%s", str);
if(str[0] == 'M') {
scanf("%d %d", &lv, &t);
if(lv & 1) {
int L = l[lv];
int R = n;
add(1, 1, n, L, R, t);
}
else {
int L = l[lv];
int R = n;
add(1, 1, n, L, R, -t);
}

}
else {
scanf("%d %d", &x, &y);
int mom = lca(x, y);
int faa = f[mom][0];
int ans = 0;
ans += find(1, 1, n, st[x]);
ans += find(1, 1, n, st[y]);
ans -= find(1, 1, n, st[mom]);
if(faa != 0)
ans -= find(1, 1, n, st[faa]);
printf("%d\n", abs(ans));

}

}

return 0;
}

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)

const int maxn=20000+10;
int n,q;
int a[maxn];

struct edge {
    int to,nxt;
} e[2*maxn];
int cnt;
int head[maxn];
int bin[30];

int sz[maxn];
int dep[maxn];
int fa[maxn][30];
int sum[maxn];
void insert(int x,int y) {
    e[++cnt]=(edge){y,head[x]},head[x]=cnt;
    e[++cnt]=(edge){x,head[y]},head[y]=cnt;
}
void dfs(int x) {
    //cout<<"!";
    //cout<<x<<endl;
    sum[x]=sum[max(0,fa[x][0])];
    if (dep[x]%2) sum[x]-=a[x];
    else sum[x]+=a[x];
    sz[x]=1;
    FOR(i,20) {
        if (dep[x]>=bin[i]) {
            fa[x][i]=fa[fa[x][i-1]][i-1];
        }
    }
    for (int i=head[x];i;i=e[i].nxt) {
        int t=e[i].to;
        if (fa[x][0]!=t) {
            fa[t][0]=x;
            dep[t]=dep[x]+1;
            dfs(t);
            sz[x]+=sz[t];
        }
    }
}
int lca(int x,int y) {
    if (dep[x]<dep[y]) swap(x,y);
    int t=dep[x]-dep[y];
    for (int i=0;i<=20;i++) {
        if (bin[i]&t) {
            x=fa[x][i];
            //t^=bin[i];
        }
    }
    for (int i=20;i>=0;i--) {
        if (fa[x][i]!=fa[y][i]) {
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    if (x==y) return x;
    else return fa[x][0];
}


struct seg {
    int l,r,v,tag;
} t[4*maxn];
void build(int k,int l,int r) {
    t[k].l=l,t[k].r=r;
    if (l==r) 
        return;
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
}

void pushdown(int k) {
    int tmp=t[k].tag;
    t[k].tag=0;
    if (t[k].l==t[k].r) return;
    t[k<<1].tag+=tmp;
    int l=t[k<<1].l,r=t[k<<1].r;
    t[k<<1].v+=(r-l+1)*tmp;
    l=t[k<<1|1].l,r=t[k<<1|1].r;
    t[k<<1|1].tag+=tmp;
    t[k<<1|1].v+=(r-l+1)*tmp;
}
void change(int k,int l,int r,int w) {
    int L=t[k].l,R=t[k].r;
    if (l==L&&r==R) {
        t[k].tag+=w;
        t[k].v+=(r-l+1)*w;
        return;
    }
    if (t[k].tag) pushdown(k);
    int mid=(L+R)>>1;
    if (r<=mid) {
        change(k<<1,l,r,w);
    } else if (l>mid) {
        change(k<<1|1,l,r,w);
    } else {
        change(k<<1,l,mid,w);
        change(k<<1|1,mid+1,r,w);
    }
    t[k].v=t[k<<1].v+t[k<<1|1].v;
}
int query(int k,int l,int r) {
    int L=t[k].l,R=t[k].r;
    if (l==L&&r==R) return t[k].v;
    int mid=(L+R)>>1;
    if (t[k].tag) {
        pushdown(k);
    }
    if (r<=mid) {
        return query(k<<1,l,r);
    } else if (l>mid) {
        return query(k<<1|1,l,r);
    } else {
        return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
    }
}
int b[maxn];

int main() {
    scanf("%d%d",&n,&q);
    FOR(i,n) 
        scanf("%d",&a[i]);
    
    int root=0;
    FOR(i,n) {
        scanf("%d",&fa[i][0]);
        if (fa[i][0]!=-1) insert(i,fa[i][0]);
        if (fa[i][0]==-1) root=i;
    }
    bin[0]=1;
    FOR(i,20) bin[i]=bin[i-1]<<1;
    dfs(root);
    
    FOR(i,n) if (dep[i]%2) a[i]=-a[i];

    //dfs2(1,1);
    build(1,1,n);
    while (q--) {
        char c;
        scanf("%s",&c);
        int x=0,y=0;
        scanf("%d%d",&x,&y);
        if (c=='M') {
            if (x%2) change(1,x,n,y);
            else change(1,x,n,-y);
            if (x%2) b[x]+=y;
            else b[x]-=y;
        } else if (c=='A') {
            int f=lca(x,y);
            int ans=sum[x]+sum[y]-2*sum[f]+a[f];
        //  int f=lca(x,y);
        //cout<<b[dep[f]+1]<<endl;
        //cout<<ans<<" " <<sum[x]<<" "<<a[f]<<endl;
        x=dep[x]+1;
        y=dep[y]+1;
        f=dep[f]+1;
            ans+=query(1,x,x)+query(1,y,y)-2*query(1,f,f)+b[f];
            //cout<<query(1,x,x)<<endl;
            printf("%d\n",abs(ans));
        }
    }
    //FOR(i,n) cout<<sum[i]<<" ";
    return 0;
}

犯了几个BUG：
1.只开了fa[maxn][20]结果访问了fa[i][20]导致下标越界
2.线段树只开了3倍大，应该要4倍，因为树高n最多=logn(上取整)+1，如果是满二叉树有2^h-1最大接近4n-1