趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
本帖最後由 jd3 於 2014-11-3 22:29 編輯
http://toj.tfcis.org/oj/pro/159/
上次大榕樹那題
WA了好多次又去Wa(挖)學長的CODE出來比較
還是找不出來WA的原因 =口=
陣列開到10倍
連不需要的long long也開了
BIT的操作看起來一樣
DFS應該不至於暴掉
範測正常的跑出268
第一筆測資過了
2,3筆都WA掉
求解QAQ
// 11.3 已解決
[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][i]] == (-1))
DFS(list[node][i]);
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[b].push_back(a);
}
DFS(1);
/*
printf("State : ");
for(int i = 1 ; i <= size ; i++)
printf("%d, ", BIT[i]);
puts("");*/
int v;
long long ans = 0;
for(int i = 1 ; i <= n ; i++)
{
scanf("%d", &value[i]);
Update(in[i], value[i]);
/*
printf("State : ");
for(int j = 1 ; j <= size ; j++)
printf("%d, ", BIT[j]);
puts("");
*/
Update(out[i], -value[i]);
/*
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[i]);
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;
}
|