一棵树呀一棵树~~~zzuli

时间：2022-08-26 21:32:52

Problem C: F

Time Limit: 1 Sec   Memory Limit: 128 MB
Submit: 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的原理很像（回溯法--）

形成一个链--线型就可以用树状数组了

。。。

表示我并不会，留下来以后补。。。(⊙.⊙)


代码：

[cpp]  view plain  copy   一棵树呀一棵树~~~zzuli 一棵树呀一棵树~~~zzuli
  1. #include<cstdio>  
  2. #include<cstring>  
  3. #include<algorithm>  
  4. using namespace std;  
  5. #define LL long long  
  6. #define MA 60000  
  7. #define lowit(x) (x&-x)  
  8. LL zhuang[2*MA];  
  9. int ru[MA],chu[MA];  
  10. int n,m,head[MA],kp;  
  11. bool fafe[MA];  
  12. struct node{  
  13.     int to,next;  
  14. }edge[MA*2];  
  15. void dfs(int xx)  
  16. {  
  17.     ru[xx]=kp++;  
  18.     fafe[xx]=false;  
  19.     for (int k=head[xx];k!=-1;k=edge[k].next)  
  20.     {  
  21.         if (fafe[edge[k].to])  
  22.             dfs(edge[k].to);  
  23.     }  
  24.     chu[xx]=kp++;  
  25.     return ;  
  26. }  
  27. void ADD(int xx,int yy)  
  28. {  
  29.     for (;xx<=n;xx+=lowit(xx))  
  30.         zhuang[xx]+=yy;  
  31. }  
  32. LL Query(int xx)  
  33. {  
  34.   LL lp=0;  
  35.   for (;xx;xx-=lowit(xx))  
  36.     lp+=zhuang[xx];  
  37.   return lp;  
  38. }  
  39. void slove()  
  40. {  
  41.     scanf("%d%d",&n,&m);  
  42.     int a,b,c;  
  43.     memset(fafe,true,sizeof(fafe));  
  44.     memset(zhuang,0,sizeof(zhuang));  
  45.     for (int i=0;i<=n;i++)  
  46.         head[i]=-1;  
  47.     for (int i=1;i<n;i++)  
  48.     {  
  49.         scanf("%d%d",&a,&b);  
  50.         edge[i*2-1].to=b;  
  51.         edge[i*2-1].next=head[a];  
  52.         head[a]=i*2-1;  
  53.         edge[i*2].to=a;  
  54.         edge[i*2].next=head[b];  
  55.         head[b]=i*2;  
  56.     }  
  57.     kp=1;n*=2;  
  58.     dfs(1);  
  59.  /*   for (int i=1;i<=n;i++)-----自坑 
  60.         printf("%d %d\n",ru[i],chu[i]);*/  
  61.     for (int i=0;i<m;i++)  
  62.     {  
  63.         scanf("%d",&c);  
  64.         if (c==1)  
  65.         {  
  66.             scanf("%d%d",&a,&b);  
  67.             if (a<0||a>n/2) continue;  
  68.             ADD(ru[a],b);  
  69.             ADD(chu[a],-b);  
  70.         }  
  71.         else  
  72.         {  
  73.             scanf("%d",&a);  
  74.             printf("%lld\n",Query(ru[a]));  
  75.         }  
  76.     }  
  77. }  
  78. int main()  
  79. {  
  80.     int t;scanf("%d",&t);  
  81.     while (t--)  
  82.         slove();  
  83.     return 0;  
  84. }  
一棵树呀一棵树~~~zzuli


标签：

相关文章