题目：

给出一个n个结点的二叉树的前序和中序遍历，初始权值为0，有如下3个操作分别
1 x val
2 x val
3 x 
分别代表 x的子树的权值都加val包括x。
根到x上的结点都减val包括x。
输出层次x的结点权值总和。不存在该层的话输出-1

输入格式:

第一行一个n，第二行和第三行分别是前序和中序遍历，接下来为m个操作。1≤n≤30,−100≤val≤100

输出格式:

对于询问3的输出结果。

输入样例:

3
2 1 3
1 2 3
3
1 2 1
2 1 10
3 1

输出样例:

9

解题思路：

中序+先序建树，bfs确定父亲结点和level，按操作add或者sub

 

ac代码：

#include <iostream>
#include <cmath>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <sstream>
#define maxn 50
#define inf 0x3fffffff
using namespace std;
typedef long long ll;
int pre[maxn],in[maxn],level[maxn],l[maxn],r[maxn],p[maxn],nodeval[maxn];
int build(int l1,int r1,int l2,int r2)
{
    if(l1>r1) return 0;
    int root=pre[l1];
    int p=0;
    while(in[p]!=root) p++;
    int len=p-l2;
    l[root]=build(l1+1,l1+len,l2,l2+len-1);
    r[root]=build(l1+len+1,r1,p+1,r2);
    return root;
}
int search(int root)
{
    int max_level=0;
    queue<int> q;
    q.push(root);
    p[root]=-1;
    level[root]=1;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        if(l[x])
        {
            q.push(l[x]);
            level[l[x]]=level[x]+1;
            p[l[x]]=x;
            max_level=level[l[x]];
        }
        if(r[x])
        {
            q.push(r[x]);
            level[r[x]]=level[x]+1;
            p[r[x]]=x;
            max_level=level[r[x]];
        }
    }
    return max_level;
}
void Add(int x,int val)
{
    if(x)
    {
        nodeval[x]+=val;
        if(l[x])  Add(l[x],val);
        if(r[x])  Add(r[x],val);
    }
}
void Sub(int x,int val)
{
    if(x!=-1)
    {
        nodeval[x]-=val;
        Sub(p[x],val);
    }
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    int n,m;
    scanf("%d",&n);
    memset(l,-1,sizeof(l));
    memset(r,-1, sizeof(r));
    memset(nodeval,0, sizeof(nodeval));
    memset(level,0, sizeof(level));
    for(int i=0;i<n;i++)
        scanf("%d",&pre[i]);
    for(int i=0;i<n;i++)
        scanf("%d",&in[i]);
    build(0,n-1,0,n-1);
    int maxl=search(pre[0]);
    //for(int i=1;i<=n;i++)
      //  cout<<p[i]<<" "<<level[i]<<endl;
    scanf("%d",&m);
    int op,x,val;
    for(int i=0;i<m;i++)
    {
        scanf("%d %d",&op,&x);
        if(op!=3) scanf("%d",&val);
        if(op==1)
            Add(x,val);
        if(op==2)
            Sub(x,val);
        if(op==3) {
            if (x <= 0 || x > maxl)
                printf("-1\n");
            else {
                int sum = 0;
                for (int j = 1; j <= n; j++)
                    if (level[j] == x)
                        sum += nodeval[j];
                 printf("%d\n",sum);
            }
        }
    }
    return 0;
}