Problem C: F
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 213 Solved: 14
Submit Status Web Board
Description
给一颗树,有n个结点,编号为1到n,1为根节点,有两种操作,1 x y把x结点权值加y,2 x查询x到根节点所有结点的权值和.
每个结点权值初始化为0。
Input
第一行输入一个整数t,代表有t组测试数据。
每组数据第一行为两个整数n,m代表结点个数和操作次数。
接下来n-1行,每行两个整数a,b,表示a结点和b结点有一条边。
接下来m行每行一个操作格式如上。
0<=n<=50000 ,0<=m<=50000,0<=y<=50000
Output
对于每组查询输出一个整数表示结果
Sample Input
1
5 5
1 2
1 3
3 4
3 5
2 5
1 1 2
1 3 1
2 4
2 1
Sample Output
0
3
2
HINT
树的近似剖分--与LCA的原理很像(回溯法--)
形成一个链--线型就可以用树状数组了
。。。
表示我并不会,留下来以后补。。。(⊙.⊙)
代码:
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- #define LL long long
- #define MA 60000
- #define lowit(x) (x&-x)
- LL zhuang[2*MA];
- int ru[MA],chu[MA];
- int n,m,head[MA],kp;
- bool fafe[MA];
- struct node{
- int to,next;
- }edge[MA*2];
- void dfs(int xx)
- {
- ru[xx]=kp++;
- fafe[xx]=false;
- for (int k=head[xx];k!=-1;k=edge[k].next)
- {
- if (fafe[edge[k].to])
- dfs(edge[k].to);
- }
- chu[xx]=kp++;
- return ;
- }
- void ADD(int xx,int yy)
- {
- for (;xx<=n;xx+=lowit(xx))
- zhuang[xx]+=yy;
- }
- LL Query(int xx)
- {
- LL lp=0;
- for (;xx;xx-=lowit(xx))
- lp+=zhuang[xx];
- return lp;
- }
- void slove()
- {
- scanf("%d%d",&n,&m);
- int a,b,c;
- memset(fafe,true,sizeof(fafe));
- memset(zhuang,0,sizeof(zhuang));
- for (int i=0;i<=n;i++)
- head[i]=-1;
- for (int i=1;i<n;i++)
- {
- scanf("%d%d",&a,&b);
- edge[i*2-1].to=b;
- edge[i*2-1].next=head[a];
- head[a]=i*2-1;
- edge[i*2].to=a;
- edge[i*2].next=head[b];
- head[b]=i*2;
- }
- kp=1;n*=2;
- dfs(1);
- /* for (int i=1;i<=n;i++)-----自坑
- printf("%d %d\n",ru[i],chu[i]);*/
- for (int i=0;i<m;i++)
- {
- scanf("%d",&c);
- if (c==1)
- {
- scanf("%d%d",&a,&b);
- if (a<0||a>n/2) continue;
- ADD(ru[a],b);
- ADD(chu[a],-b);
- }
- else
- {
- scanf("%d",&a);
- printf("%lld\n",Query(ru[a]));
- }
- }
- }
- int main()
- {
- int t;scanf("%d",&t);
- while (t--)
- slove();
- return 0;
- }