1741.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

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

long  use[14];
long  lchild[10010][14];
long  rchild[10010][14];
long  sum[510010][14];
long  depth[10010][14];

long  value[10010],dist[10010];
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[10020*2];

long begin[10020],end[10020];


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

long stack[10010],st,ii[10010];
bool init()
{
	scanf("%ld %ld",&n,&k);
	if(n==0&&k==0)return 0;

	m=n-1;
	long i,j;

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

		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<14;i++)
	{
		use[i]=0;
		for(j=0;j<n;j++)
		{
			rchild[j][i]=lchild[j][i]=-1;
			sum[j][i]=0;
		}
	}
	long now,*father=value;
	st=1;stack[0]=0;ii[0]=-1;dist[0]=0;

	while(st)
	{
		now=stack[--st];
		ii[st]++;
		if(ii[st]<end[now]&&e[ii[st]].to==father[now])
			ii[st]++;
		
		if(ii[st]<end[now])
		{
			stack[st+1]=e[ii[st]].to;
			father[stack[st+1]]=now;
			ii[st+1]=begin[stack[st+1]]-1;
			dist[stack[st+1]]=dist[now]+e[ii[st]].distance;
			st+=2;
		}
	}
	
	copy(&dist[0],&dist[n],&value[0]);
	sort(&value[0],&value[n]);
	
	for(i=1,kind=1;i<n;i++)
	if(value[i]!=value[i-1])value[kind++]=value[i];	

	answer=0;
	return 1;
}

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

}


void doit()
{
	long now,child;long tree[40010];long father[40010];
	
	st=1;stack[0]=0;ii[0]=-1;tree[0]=0;
	great(dist[0]);father[0]=0;
	while(st)
	{
		now=stack[--st];
		ii[st]++;
		
		if(ii[st]<end[now]&&e[ii[st]].to==father[now])
				ii[st]++;
		if(ii[st]<end[now])
		{
			child=e[ii[st]].to;
			father[child]=now;
			tree[child]=use[0];
			great(dist[child]);
			
			
			stack[st+1]=child;
			ii[st+1]=begin[child]-1;
			st+=2;
		}
		else if(st)
		{
			if(sum[tree[now]][0]<sum[tree[stack[st-1]]][0])
			{
				count(tree[stack[st-1]],tree[now],0,dist[stack[st-1]]*2);
				merge(tree[stack[st-1]],tree[now],0);
			}
			else
			{
				count(tree[now],tree[stack[st-1]],0,dist[stack[st-1]]*2);
				merge(tree[now],tree[stack[st-1]],0);
				tree[stack[st-1]]=tree[now];
			}
		}
	}
	printf("%ld\n",answer);
	return ;
}

int main()
{
	while(init())
	doit();

	return 0;
}