[問] TOJ - 159

jd3

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;
}