#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <utility>
#include <cmath>
#define INF 1000000000
using namespace std;
typedef pair< long , long > Enode;
long N,Q,S;
vector< Enode > ta[300005];
long vis[300005],Vn;
long Line1[300005];
long Line2[300005];
long RA[300005][20];
long size[300005];
long height[300005];
long where[300005];
long logt[300005];
long A[300005],B[300005];
long Tsum[300005];
void add(long x,long y)
{
     while(x<=N)
     {
         Tsum[x]+=y;
         x+=(x&-x);
     }
}
long sum(long x)
{
     long res=0;
     while(x>0)
     {
         res+=Tsum[x];
         x-=(x&-x);
     }
     return res;
}
void dfs(long x,long len,long ht)
{
     vector< Enode >::iterator it;
     vis[x]=Vn;
     Line1[x]=++Line1[0];
     Line2[++Line2[0]]=x;
     where[x]=Line2[0];
     height[x]=ht;
     add(Line1[x],len);
     add(Line1[x]+1,-len);
     for(it=ta[x].begin();it!=ta[x].end();it++)   
         if(vis[it->first]!=Vn)
             {
                 dfs(it->first,len+it->second,ht+1);
                 Line2[++Line2[0]]=x;
                 size[x]+=size[it->first];
             }
     size[x]++;
}
void buildRA()
{
     long i,j;
     logt[1]=0;
     for(i=2;i<=Line2[0];i++)
         if((i&(i-1))==0) logt[i]=logt[i-1]+1;
         else logt[i]=logt[i-1];
     for(i=1;i<=Line2[0];i++)
         RA[i][0]=Line2[i];
     for(i=Line2[0];i>=1;i--)
         for(j=1;i+(1<<j)-1<=Line2[0];j++)
             if(height[RA[i][j-1]]<height[RA[i+(1<<(j-1))][j-1]]) RA[i][j]=RA[i][j-1];