【bzoj2599】[IOI2011]Race 点分治

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<iostream>
#define maxn 200100 

using namespace std;

struct yts
{
	int d1,d2;
}st[maxn];

int head[maxn],to[2*maxn],next[2*maxn],len[2*maxn],dis[maxn],dep[maxn];
int size[maxn],ans[maxn],fa[maxn];
bool vis[maxn];
int n,m,num,k,top;

bool cmp(yts x,yts y)
{
	return x.d1<y.d1;
}

void addedge(int x,int y,int z)
{
	num++;to[num]=y;len[num]=z;next[num]=head[x];head[x]=num;
}

void get_root(int x,int Size,int &cg)
{
	bool flag=1;
	size[x]=1;
	for (int p=head[x];p;p=next[p])
	  if (!vis[to[p]] && to[p]!=fa[x])
	  {
	  	fa[to[p]]=x;
	  	get_root(to[p],Size,cg);
	  	size[x]+=size[to[p]];
	  	if (size[to[p]]>Size/2) flag=0;
	  }
	if (Size-size[x]>Size/2) flag=0;
	if (flag) cg=x;
}

void dfs1(int x,int d1,int d2)
{
	dis[x]=d1;dep[x]=d2;
	for (int p=head[x];p;p=next[p])
	  if (!vis[to[p]] && to[p]!=fa[x]) fa[to[p]]=x,dfs1(to[p],d1+len[p],d2+1);
}

void dfs2(int x)
{
	st[++top].d1=dis[x];st[top].d2=dep[x];
	for (int p=head[x];p;p=next[p])
	  if (!vis[to[p]] && to[p]!=fa[x]) dfs2(to[p]);
}

void calc(int x,int f)
{
	top=0;
	dfs2(x);
	sort(st+1,st+top+1,cmp);
	for (int i=1,j=top;i<=j;i++)
	{
		while (j>i && st[i].d1+st[j].d1>k) j--;
		for (int p=j;st[i].d1+st[p].d1==k;p--) ans[st[i].d2+st[p].d2]+=f;
	}
}

void solve(int x,int Size)
{
	int cg;
	fa[x]=0;
	get_root(x,Size,cg);
	size[fa[cg]]=Size-size[cg];
	fa[cg]=0;vis[cg]=1;
	dfs1(cg,0,0);
	calc(cg,1);
	for (int p=head[cg];p;p=next[p]) if (!vis[to[p]]) calc(to[p],-1);
	for (int p=head[cg];p;p=next[p]) if (!vis[to[p]]) solve(to[p],size[to[p]]);
}

int main()
{
	scanf("%d%d",&n,&k);
	for (int i=1;i<n;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		x++;y++;
		addedge(x,y,z);addedge(y,x,z);
	}
	solve(1,n);
	for (int i=1;i<n;i++) if (ans[i]) {printf("%dn",i);return 0;}
	printf("-1n");
	return 0;
}