Hello
I am getting wrong answer in problem Tree
I am using Heavy light decomposition
but i keep getting WA in test #3
can you please check my code or pleaaase give my tricky testcases
#include <iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<utility>
#define P(x,y) make_pair(x,y)
using namespace std;
const int MX=60001;
vector< pair<int,int> >v[MX];
int n,mx=0,a,b,c,it=0,Q;
int par[MX],sz[MX],skip[MX],in[MX],out[MX],depth[MX],val[MX],arr[MX],chain[MX],sum[MX],ans;
bool is[MX];
void dfs(int x){
    int s=v[x].size();
    for(int j=0;j<s;j++){
        int nxt=v[x][j].first;
        if(nxt==par[x]) continue;
        par[nxt]=x; depth[nxt]=depth[x]+1;
        val[nxt]=v[x][j].second;
        dfs(nxt);
        sz[x]+=sz[nxt];
    }
}
void heavy_light(int x){
    int s=v[x].size();
    for(int j=0;j<s;j++){
        int nxt=v[x][j].first;
        if(nxt==par[x]) continue;
        if(sz[nxt]>sz[x]/2){
            is[nxt]=1;
            mx++; in[nxt]=mx; out[x]=mx; arr[mx]=val[nxt];
            if(skip[x]==-1){
                chain[nxt]=++it;
                skip[nxt]=x;
            }
            else{
                chain[nxt]=chain[x];
                skip[nxt]=skip[x];
            }

        }
        heavy_light(nxt);
    }
}
void LCA(){
    while(1){
        if(depth[a]<depth[b]) swap(a,b);
        if(depth[a]==depth[b]&&is[a]) swap(a,b);
        if(a==b) break;
        if(chain[a]==chain[b]&&chain[a]!=-1){
            ans+=sum[in[a]]-sum[out[b]-1];
            break;
        }
        if(!is[a]){
            ans+=val[a];
            a=par[a];
        }
        else{
            ans+=sum[in[a]]-sum[out[skip[a]]-1];
            a=skip[a];
        }

    }
    printf("%d\n",ans);
}
int main(){

   // freopen("in.in","r",stdin);
    scanf("%d",&n);
    for(int j=1;j<=n;j++){
        sz[j]=1;
        skip[j]=in[j]=out[j]=chain[j]=par[j]=-1;
        is[j]=0;
    }
    for(int j=1;j<n;j++){
        scanf("%d %d %d",&a,&b,&c); a++; b++;
        v[a].push_back(P(b,c));
        v[b].push_back(P(a,c));
    }
    depth[1]=1;
    dfs(1);
    heavy_light(1);
    sum[0]=0;
    for(int j=1;j<=mx;j++) sum[j]=arr[j]+sum[j-1];
    scanf("%d",&Q);
    while(Q--){
        ans=0;
        scanf("%d %d",&a,&b); a++; b++;
        LCA();
    }
    return 0;
}


Edited by author 17.05.2013 07:45