记录编号	264114	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[BZOJ3653]谈笑风生	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	11.194 s
提交时间	2016-05-27 18:07:47	内存使用	197.65 MiB

#include<stdio.h>
#define fastcall __attribute__((optimize("-O3")))
#define IL  __inline__ __attribute__((always_inline))
#define ll long long
ll ans;
fastcall IL void in(int&x){for(x=getchar();x<48|x>57;x=getchar());x^=48;for(int tmp=getchar();47<tmp&tmp<58;tmp=getchar())x=x*10+(tmp^48);}
int n,m,k,mxdep,shu,first[300010];
struct edge{int v,nx;}o[600010];
fastcall IL void add(int u,int v){
    o[++shu].v=v,o[shu].nx=first[u],first[u]=shu;
}
int id[300010],rid[300010],s[300010],dep[300010];
fastcall inline void dfs(int x,int last){
    if(mxdep<dep[x])mxdep=dep[x];
    s[x]=1,id[x]=++id[0],rid[id[0]]=x;
    for(int i=first[x];i;i=o[i].nx)if(o[i].v!=last)
        dep[o[i].v]=dep[x]+1,dfs(o[i].v,x),s[x]+=s[o[i].v];
}
int cnt1,rt1[300010],ls1[6000010],rs1[6000010];
ll tr1[6000010];
fastcall inline void ADD1(int l,int r,int t,int tt,int x){
    tr1[t]=tr1[tt]+1;
    if(l==r)return;
    int mid=l+r>>1;
    if(x<=mid){
        if(!ls1[t])ls1[t]=++cnt1;
        rs1[t]=rs1[tt];
        ADD1(l,mid,ls1[t],ls1[tt],x);
    }else{
        if(!rs1[t])rs1[t]=++cnt1;
        ls1[t]=ls1[tt];
        ADD1(mid+1,r,rs1[t],rs1[tt],x);
    }
}
int cnt2,rt2[300010],ls2[6000010],rs2[6000010];
ll tr2[6000010];
fastcall inline void ADD2(int l,int r,int t,int tt,int x){
    tr2[t]=tr2[tt]+x;
    if(l==r)return;
    int mid=l+r>>1;
    if(x<=mid){
        if(!ls2[t])ls2[t]=++cnt2;
        rs2[t]=rs2[tt];
        ADD2(l,mid,ls2[t],ls2[tt],x);
    }else{
        if(!rs2[t])rs2[t]=++cnt2;
        ls2[t]=ls2[tt];
        ADD2(mid+1,r,rs2[t],rs2[tt],x);
    }
}
fastcall inline ll sum1(int l,int r,int t,int tt,int L,int R){
    if(L<=l&&r<=R)return tr1[t]-tr1[tt];
    int mid=l+r>>1;
    if(R<=mid)return sum1(l,mid,ls1[t],ls1[tt],L,R);
    if(L>mid)return sum1(mid+1,r,rs1[t],rs1[tt],L,R);
    return sum1(l,mid,ls1[t],ls1[tt],L,R)+sum1(mid+1,r,rs1[t],rs1[tt],L,R);
}
fastcall inline ll sum2(int l,int r,int t,int tt,int L,int R){
    if(L<=l&&r<=R)return tr2[t]-tr2[tt];
    int mid=l+r>>1;
    if(R<=mid)return sum2(l,mid,ls2[t],ls2[tt],L,R);
    if(L>mid)return sum2(mid+1,r,rs2[t],rs2[tt],L,R);
    return sum2(l,mid,ls2[t],ls2[tt],L,R)+sum2(mid+1,r,rs2[t],rs2[tt],L,R); 
}
int main(){
	freopen("laugh.in","r",stdin);
	freopen("laugh.out","w",stdout);
    in(n),in(m);
    for(int i=1,u,v;i<n;++i)
        in(u),in(v),add(u,v),add(v,u);
    dfs(1,1);
    for(int i=1;i<=n;++i)
        ADD1(0,mxdep,rt1[i]=++cnt1,rt1[i-1],dep[rid[i]]);
    for(int i=1;i<=n;++i)
        ADD2(0,mxdep,rt2[i]=++cnt2,rt2[i-1],dep[rid[i]]);
    for(int i=1,x;i<=m;++i){
        in(x),in(k);
        ans=0;
        if(k){
            ans+=sum2(0,mxdep,rt2[id[x]+s[x]-1],rt2[id[x]],dep[x]+1,dep[x]+k);
            ans-=sum1(0,mxdep,rt1[id[x]+s[x]-1],rt1[id[x]],dep[x]+1,dep[x]+k)*(dep[x]+1);   
        }
        if(dep[x]+k<mxdep)ans+=sum1(0,mxdep,rt1[id[x]+s[x]-1],rt1[id[x]],dep[x]+k+1,mxdep)*k;
        if(k>dep[x])k=dep[x];
        ans+=(ll)k*(s[x]-1);
        printf("%lld\n",ans);
    }
}