你的工资是多少时间限制(普通/Java) : 2000 MS/ 6000 MS 运行内存限制 : 65536 KByte
总提交 : 9 测试通过 : 3 描述
民大ACM团队毕业的成员，聚到一起开了一家IT公司。营业期间，公司的利润也是时而涨时儿跌，大家不得不感叹创业之艰辛。 当然，作为ACMer出身，公司对工资的调整是非常严谨的，按团队或个人贡献，进行严格审批。 公司的共有n个员工，每个员工的编号分别是Di（1<=i<=n），并且公司中有着严格的团队分类制度。每个下属有且只有一个直属上司，每个上司可能有多个下属。公司中只有一个总裁，并且总裁为D1，即i=1。除了总裁之外，所有员工都有自己的上司。 现在，公司请你帮忙写一个工资管理系统。 它需要具备一下功能： 1、查询Di目前的工资。 2、为Di加薪x元（-10000000 <= x <= 10000000）。 3、将Di所带领的团队中的每个人，各加薪x元。（Di的所带领的团队表示：Di 及 Di的下属团） 注意：每个人的初始工资都是0 。
输入
多组测试数据。 每组测试数据第一行有一个整数n，代表员工数量。（0<n<=100000）。 接下来n-1行，每行输入两个整数i、j（0<i,j<=n），表示Di的上司是Dj。 接下来输入一个整数m，代表操作的数量。（0<m<=100000）。 接下来m行，每行表示一个操作： 1. 输入 Query i ，表示查询Di的工资。 2. 输入 Add i x ，表示将 Di的加薪x元。 3. 输入 All i x ，表示将Di带领的团队，每个人加薪x元。
输出 对于操作中的每一个询问，输出相应的答案。 样例输入 4 样例输出 3 |
http://218.194.91.48/acmhome/problemdetail.do?&method=showdetail&id=1440
这题的方法是 DFS +
树状数组（或者 DFS + 线段树（因为树状数组能做的，线段树都能做么））。。。
那么，DFS遍历的过程，主要是为了【树化区间】，大家可以看一下下图：
转化成区间之后，就是：
像不像将最上面那棵树，往左弯曲？
其实，DFS遍历的时候，就是按照 1、2、5、6、7、9、10、8、11、4、3，这样的顺序来访问各个节点。
于是，我们只需要记录每个节点的[起始点的位置]start，以及能够延伸到的[最远点的位置]end，那么，这个节点以及其所有的子节点，就是[start,end]
这个区间。
比如节点1，其区间是[1，11]；节点2的区间[2，5]；节点9的区间[6,9]；节11的区间[9,9]
。
将树转化成区间之后，那么剩下的就是区间更新、单点查询了（可以参照专题【树状数组】挖坑- 1002）。
因此，利用非常基础的树状数组或者线段树，很容易就能解决了。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;
struct Edge{
int to,next;
}eg[100010];
int Ecnt,Ef[100010],top;
void add_Edge(){
int a,b;
scanf("%d%d",&a,&b);
eg[Ecnt].to=a;
eg[Ecnt].next=Ef[b];
Ef[b]=Ecnt++;
}
int newID,Start[100010],End[100010];
void dfs(int v){
Start[v]=++newID;
for(int k=Ef[v];k!=-1;k=eg[k].next){
dfs(eg[k].to);
}
End[v]=newID;
}
__int64 tree[100010];
int lowbit(int x){
return x&-x;
}
__int64 query(int v){
__int64 sum=0;
while(v<=n){
sum+=tree[v];
v+=lowbit(v);
}
return sum;
}
void update(int v,int val){
while(v>0){
tree[v]+=val;
v-=lowbit(v);
}
}
void _init(){
int i;
Ecnt=0;
newID=0;
for(i=1;i<=n;i++){
Ef[i]=-1;
tree[i]=0;
Start[i]=-1;
}
}
int main(){
int i,x;
char op[10];
while(~scanf("%d",&n)){
_init();
for(i=1;i<n;i++) add_Edge();
dfs(1);
scanf("%d",&m);
while(m--){
scanf("%s",op);
if(op[0]=='Q'){
scanf("%d",&i);
printf("%I64d\n",query(Start[i]));
}
else if(op[1]=='d'){
scanf("%d%d",&i,&x);
update(Start[i],x);
update(Start[i]-1,-x);
}
else{
scanf("%d%d",&i,&x);
update(End[i],x);
update(Start[i]-1,-x);
}
}
}
return 0;
}