清北学堂 三部曲

三部曲
【问题描述】
因为外来的入侵，国王决定在某些城市加派士兵。所有城市初始士兵数量为
0。当城市?被加派了?名士兵时。城市?的所有子城市需要被加派? + 1名士兵。这
些子城市的所有子城市需要被加派? +2名士兵。以此类推。
当然，加派士兵的同时，国王也需要不断了解当前的情况。于是他随时可能
询问以城市 i 为根的子树中的所有城市共被加派了多少士兵。
你现在是国王的军事大臣，你能回答出国王的每个询问么？
【输入格式】
第一行，包含两个整数?,?代表城市数量以及国王的命令的数量。
第二行? −1个整数，表示2− ?号每个节点的父亲节点。
接下来的?行，每行代表国王的一个命令，命令分两种:
? ? ? 在城市?加入?个士兵
? ? 询问以城市?为根的子树中所有士兵数量的和。
【输出格式】
对于每个?，输出答案。
【样例输入】
7 10
1 1 2 2 5 5
Q 1
A 2 1
Q 1
Q 2
Q 5
A 5 0
Q 5
A 3 1
Q 1
Q 2
【样例输出】
0
11
11
8
10
14
13
【样例解释】
无。
【数据规模与约定】
对于50%的数据，1 ≤ ? ≤ 1000 1≤ ? 300。
对于100%的数据，1 ≤ ? ≤ 50000 1≤ ? ≤ 100000 1≤ ? ≤ ? 0 ≤ ? ≤
1000。

/*线段树+暴力+乱搞 50分*/
#include <cstdio>
#include <cstring>
#define MAXN 50010
using namespace std;
struct link
{
    int to;
    int nxt;
}e[2*MAXN];
int n,T,x,y,cnt;
int edge_num[MAXN];
int father[MAXN];
long long num[MAXN];
char opt[3];

void add(int u,int v)
{
    e[cnt]=(link){v,edge_num[u]};edge_num[u]=cnt++;
    e[cnt]=(link){u,edge_num[v]};edge_num[v]=cnt++;
}

void add(int node,int father,int delta)
{
    num[node]+=delta;
    for (int i=edge_num[node];~i;i=e[i].nxt)
        if (e[i].to!=father) add(e[i].to,node,delta+1);
}

long long query(int node,int father)
{
    long long res=0;
    for (int i=edge_num[node];~i;i=e[i].nxt)
        if (e[i].to!=father) res+=query(e[i].to,node);
    return res+num[node];
}

int main()
{
    freopen("truetears.in","r",stdin);freopen("truetears.out","w",stdout);
    memset(edge_num,-1,sizeof(edge_num));
    scanf("%d %d",&n,&T);
    for (int i=2;i<=n;i++)
    {
        scanf("%d",&x);
        father[i]=x;add(x,i);
    }
    father[1]=1;
    while (T--)
    {
        scanf("%s",opt);
        if (opt[0]=='A')
        {
            scanf("%d %d",&x,&y);
            add(x,father[x],y);
        }
        else
        {
            scanf("%d",&x);
            long long ans=query(x,father[x]);
            printf("%I64d
",ans);
        }
    }
    return 0;
}