bzoj 3653

  1 /**************************************************************
  2     Problem: 3653
  3     User: idy002
  4     Language: C++
  5     Result: Accepted
  6     Time:9276 ms
  7     Memory:114596 kb
  8 ****************************************************************/
  9  
 10 #include <cstdio>
 11 #define min(a,b) ((a)<(b)?(a):(b))
 12 #define N 300010
 13 #define S 6000000
 14  
 15 typedef long long dnt;
 16  
 17 struct Node {
 18     dnt v;
 19     Node *ls, *rs;
 20 }pool[S], *tail=pool, *null=tail, *root[N];
 21  
 22 int n, m;
 23 int head[N], dest[N+N], next[N+N], etot;
 24 int fat[N], dep[N], siz[N], in[N], out[N], vin[N], idc, mdep;
 25  
 26 void adde( int u, int v ) {
 27     etot++;
 28     next[etot] = head[u];
 29     dest[etot] = v;
 30     head[u] = etot;
 31 }
 32 void dfs( int u ) {
 33     idc++;
 34     in[u] = idc;
 35     vin[idc] = u;
 36     siz[u] = 1;
 37     for( int t=head[u]; t; t=next[t] ) {
 38         int v=dest[t];
 39         if( v==fat[u] ) continue;
 40         fat[v] = u;
 41         dep[v] = dep[u]+1;
 42         dfs(v);
 43         siz[u] += siz[v];
 44     }
 45     out[u] = idc;
 46     if( dep[u]>mdep ) mdep=dep[u];
 47 }
 48 inline void update( Node *nd ) {
 49     nd->v = nd->ls->v + nd->rs->v;
 50 }
 51 Node *modify( Node *snd, int lf, int rg, int pos, int delta ) {
 52     Node *nnd = ++tail;
 53     if( lf==rg ) {
 54         nnd->v = snd->v + delta;
 55         return nnd;
 56     }
 57     int mid=(lf+rg)>>1;
 58     if( pos<=mid ) {
 59         nnd->ls = modify( snd->ls, lf, mid, pos, delta );
 60         nnd->rs = snd->rs;
 61     } else {
 62         nnd->ls = snd->ls;
 63         nnd->rs = modify( snd->rs, mid+1, rg, pos, delta );
 64     }
 65     update( nnd );
 66     return nnd;
 67 }
 68 dnt query( Node *nd, int lf, int rg, int L, int R ) {
 69     if( nd==null ) return 0LL;
 70     if( L<=lf && rg<=R ) 
 71         return nd->v;
 72     int mid=(lf+rg)>>1;
 73     dnt rt = 0LL;
 74     if( L<=mid ) rt += query( nd->ls, lf, mid, L, R );
 75     if( R>mid ) rt += query( nd->rs, mid+1, rg, L, R );
 76     return rt;
 77 }
 78 void build() {
 79     null->ls = null->rs = null;
 80     null->v = 0;
 81     root[0] = null;
 82     for( int i=1; i<=idc; i++ ) {
 83         root[i] = modify( root[i-1], 1, mdep, dep[vin[i]], siz[vin[i]]-1 );
 84     }
 85 }
 86 dnt query( int u, int k ) {
 87     dnt ans1 = (dnt) min(k,dep[u]-1) * (siz[u]-1);
 88     dnt ans2 = 0LL;
 89     if( siz[u]==1 ) return ans1;
 90  
 91     ans2 += query( root[out[u]], 1, mdep, dep[u]+1, min( dep[u]+k, mdep ) );
 92     ans2 -= query( root[in[u]], 1, mdep, dep[u]+1, min( dep[u]+k, mdep ) );
 93     return ans1 + ans2;
 94 }
 95 int main() {
 96     scanf( "%d%d", &n, &m );
 97     for( int i=1,u,v; i<n; i++ ) {
 98         scanf( "%d%d", &u, &v );
 99         adde( u, v );
100         adde( v, u );
101     }
102     fat[1] = 1;
103     dep[1] = 1;
104     dfs(1);
105     build();
106     for( int t=1,u,k; t<=m; t++ ) {
107         scanf( "%d%d", &u, &k );
108         printf( "%lld\n", query(u,k) );
109     }
110 }