Poj Solution 1987

http://poj.org/problem?id=1987

#include"stdio.h"
#include"algorithm"
using namespace std;

long  use[16];
long  father[40010];
long  queue[40010];
long  lchild[40010][16];
long  rchild[40010][16];
long  sum[40010][16];
long  depth[40010][16];

long  value[40010],dist[40010];
long  m,n,k,kind,answer;

long findit(long key,long s1,long deep)
{ 
    long &lc=lchild[s1][deep],&rc=rchild[s1][deep],sumnow=sum[s1][deep];
    long now=depth[s1][deep];

    if(now==key)
    {
        if(rc>=0)return sumnow-sum[rc][deep+1];
        else return sumnow;
    }

    else if(key<now)
    {
        if(lc>=0)return findit(key,lc,deep+1);
        return 0;
    }
    else 
    {
        if(rc>=0)return sumnow-sum[rc][deep+1]+findit(key,rc,deep+1);
        return sumnow;
    }
}

void merge(long s1,long s2,long deep)
{ 
    long &lc=lchild[s1][deep],&rc=rchild[s1][deep];
    long &lc2=lchild[s2][deep],&rc2=rchild[s2][deep];

    sum[s1][deep]+=sum[s2][deep];
            
    if(lc<0)lc=lc2;
    else 
    {
        if(lc2>=0)merge(lc,lc2,deep+1);
    }
    
    if(rc<0)rc=rc2;
    else 
    {
        if(rc2>=0)merge(rc,rc2,deep+1);
    }
}

void great(long key)
{
    long down=0,up=kind-1,deep=0,c,*p=0;
    while(1)
    {
        c=(down+up)/2;
        depth[use[deep]][deep]=value[c];
        sum[use[deep]][deep]=1;
        if(p)*p=use[deep];
        use[deep]++;
                
        if(value[c]==key)break;
        else if(key<value[c]){up=c-1;p=&lchild[use[deep]-1][deep];}
        else {down=c+1;p=&rchild[use[deep]-1][deep];}
        deep++;
    }
}

////////////////////////////////////////////////////////
struct edge
{
    long from,to;
    long distance;
}e[40020*2];

long begin[40020],end[40020];


int cmp(edge a,edge b)
{
    return a.from<b.from||(a.from==b.from&&a.to<b.to);
}

void init()
{
    scanf("%ld %ld",&n,&m);

    long i,j;char c;

    for(i=0;i<2*m;i+=2)
    {
        scanf("%ld %ld %ld %c",&e[i].from,&e[i].to,&e[i].distance,&c);

        e[i].from--;
        e[i].to--;

        e[i+1].from=e[i].to;
        e[i+1].to=e[i].from;
        e[i+1].distance=e[i].distance;
    }

    sort(&e[0],&e[m*2],cmp);
    
    begin[0]=0;
    for(i=1;i<m*2;i++)
    {
        if(e[i].from!=e[i-1].from)
        {
            end[e[i-1].from]=i;
            begin[e[i].from]=i;
        }
    }
    end[n-1]=2*m;
    scanf("%ld",&k);
    
    for(i=0;i<16;i++)
    {
        use[i]=0;
        for(j=0;j<n;j++)
        {
            rchild[j][i]=lchild[j][i]=-1;
            sum[j][i]=0;
        }
    }
    long now,qh=0,qt=1;
    dist[0]=0;queue[0]=0;father[0]=-1;

    while(qh<qt)
    {
        now=queue[qh++];
        for(i=begin[now];i<end[now];i++)
        if((j=e[i].to)!=father[now])
        {
            queue[qt++]=j;
            father[j]=now;
            dist[j]=dist[now]+e[i].distance;
        }
    }
    
    copy(dist,dist+n,value);
    sort(value,value+n);
    
    for(i=1,kind=1;i<n;i++)
    if(value[i]!=value[i-1])value[kind++]=value[i];    

    answer=0;
    return;
}

void countit(long t,long s,int deep,long l)
{
    long a=sum[s][deep],lc=lchild[s][deep],rc=rchild[s][deep];
        
    if(lc>=0)
    {
        a-=sum[lc][deep+1];
        countit(t,lc,deep+1,l);
    }
    
    if(rc>=0)
    {
        a-=sum[rc][deep+1];
        countit(t,rc,deep+1,l);
    }
    
    if(a>0)
    {
        answer+=a*findit(k+l-depth[s][deep],t,0);
    }
    
    return;

}

void doit()
{
    long s,f,i,l,tree[40010];
    
    for(i=0;i<n;i++)
    {
        tree[i]=i;
        great(dist[i]);
    }
    for(i=n-1;i>0;i--)
    {   
        s=queue[i];
        f=father[s];
        l=dist[f]*2;
        if(sum[tree[s]][0]<sum[tree[f]][0])
        {
            countit(tree[f],tree[s],0,l);
            merge(tree[f],tree[s],0);
        }
        else
        {    
            countit(tree[s],tree[f],0,l);
            merge(tree[s],tree[f],0);
            tree[f]=tree[s];
        }
    }
    
    printf("%ldn",answer);
    return ;
}

int main()
{
    init();
    doit();
    return 0;
}