BZOJ2599: [IOI2011]Race 点分治

题目链接：http://www.lydsy.com/JudgeOnline/PRoblem.php?id=2599

题解：点分治的时候记录两个值，一个是距离，一个是边数，因为最小值是无法删除的，所以可以开一个数组记录每一个答案出现了多少次，最后从小到大扫数组就OK

#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int N=200005;const int M=400005;const int inf=1e9;struct pp{int dis,dep;} s[N];int len,n,K,G,h,sum,cnt,dep[N],dis[N],siz[N],maxn,ans[N];int to[M],nxt[M],lj[N],w[M];bool vis[N];void ins(int f,int t,int p) {cnt++,to[cnt]=t,nxt[cnt]=lj[f],lj[f]=cnt,w[cnt]=p;}void add(int f,int t,int p) {ins(f,t,p),ins(t,f,p);}bool cmp(pp u,pp v) {return u.dis<v.dis;}void dfs(int x,int fa){	s[++h]=(pp){dis[x],dep[x]};	for(int i=lj[x];i;i=nxt[i])	if(!vis[to[i]]&&to[i]!=fa)	{		dis[to[i]]=dis[x]+w[i];		dep[to[i]]=dep[x]+1;		dfs(to[i],x);	}}void findG(int x,int fa){	int mx=0;	siz[x]=1;	for(int i=lj[x];i;i=nxt[i])	if(!vis[to[i]]&&to[i]!=fa)	{		findG(to[i],x);		siz[x]+=siz[to[i]];		mx=max(mx,siz[to[i]]);	}	mx=max(mx,sum-siz[x]);	if(mx<maxn) maxn=mx,G=x;}void cal(int x,int now,int ff){	dis[x]=now;	h=0;	dfs(x,0);	sort(s+1,s+h+1,cmp);	int j=h;	for(int i=1;i<=h;i++)      {    	while(s[i].dis+s[j].dis>K) j--;        for(int l=j;K&&s[i].dis+s[l].dis==K;l--)        ans[s[i].dep+s[l].dep]+=ff;    }}void solve(int x){	dep[x]=0;	cal(x,0,1);	vis[x]=true;	for(int i=lj[x];i;i=nxt[i])	if(!vis[to[i]])	{		cal(to[i],w[i],-1);		maxn=inf;		sum=siz[to[i]];		findG(to[i],0);		solve(G);	}}int main(){	scanf("%d%d",&n,&K);	int u,v,w;	for(int i=1;i<n;i++)	{		scanf("%d%d%d",&u,&v,&w);		u++,v++;		add(u,v,w);	}	G=0;	sum=n,maxn=inf;	findG(1,0);	solve(G);	for(int i=1;i<=n;i++)	if(ans[i])	{		printf("%d/n",i);		return 0;	}	puts("-1");}