[C++] 純文本查看 復制代碼
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int n;
vector<int> list[500100];
int in[500100];
int out[500100];
int value[500100];
int BIT[2000000];
int size=0;
void Update(int a, int x)
{
while(a <= size)
{
BIT[a] += x;
a += (a&(-a));
}
}
int Sum(int a)
{
int ans=0;
while(a > 0)
{
ans += BIT[a];
// printf("at BIT[%d] : %d\n", a, BIT[a]);
a -= (a&(-a));
}
return ans;
}
void DFS(int node)
{
in[node] = ++size;
// printf("[%d] in %d\n", size, node);
for(int i = 0 ; i < list[node].size() ; i++)
if(in[list[node]] == (-1))
DFS(list[node]);
out[node] = ++size;
// printf("[%d] out %d\n", size, node);
}
int main()
{
int m;
int a,b;
char str[100];
memset(in, -1, sizeof(in));
scanf("%d%d",&n,&m);
for(int i = 1 ; i < n ; i++)
{
scanf("%d%d",&a,&b);
list[a].push_back(b);
list.push_back(a);
}
DFS(1);
/*
printf("State : ");
for(int i = 1 ; i <= size ; i++)
printf("%d, ", BIT);
puts("");*/
int v;
long long ans = 0;
for(int i = 1 ; i <= n ; i++)
{
scanf("%d", &value);
Update(in, value);
/*
printf("State : ");
for(int j = 1 ; j <= size ; j++)
printf("%d, ", BIT[j]);
puts("");
*/
Update(out, -value);
/*
printf("State : ");
for(int j = 1 ; j <= size ; j++)
printf("%d, ", BIT[j]);
puts("");
*/
}
/*
printf("State : ");
for(int i = 1 ; i <= size ; i++)
printf("%d, ", BIT);
puts("");
*/
for(int i = 0 ; i < m ; i++)
{
scanf("%s", str);
if(str[0] == 'C')
{
scanf("%d%d", &a, &b);
Update(in[a], b-value[a]);
Update(out[a], (-b)+value[a]);
}
else
{
scanf("%d", &a);
ans += Sum(in[a]);
}
}
printf("%lld\n", ans);
return 0;
}