Tang-Dreamoon's Blog

bzoj 2599 Race

发表于 | 分类于 ， ，

点分治入门（二）

　　题目链接：bzoj 2599

　　题意：写 B z o j 的题意就是简单——题意见上……

　　题解：首先我们在大体上使用点分治的做法，然后考虑每一层如何做。在这里我选择了数组指针扫描法：假设扫描时两个指针指向了 X、Y 两个点，那么我们需要让 W[X]+W[Y]=K 而且 B[X]≠B[Y]，这时用该路径的边数更新答案即可。这时我们发现，如果左指针确定后，满足 W[X]+W[Y]=K 的右指针的范围对应一个权值区间。为了避免枚举这些左指针时，对于右指针的区间重复枚举，可以对每个区间记录路径边数的最小值和次小值，且保证这两个值所对应的 Belong 不一样。这样在枚举左指针时，可供选择的右指针不是最小值就是次小值。

　　我思故我在：点分治的题目，一如既往的难在对于每一层的状态的处理上。这次又被坑了不少时间：既然选择要记录每一个权值区间的边数的最小次小值，那么就一定得处理好这两个值之间的 Belong 的关系。我错在了直接给次大值赋值的时候，忘记去判断新的次大值的 Belong 是否与最大值的不同，导致Wa了两次。⊙__⊙b汗~

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,k;
int head,mina;
int tot=0;
int ans=2147483647;
struct table{
	int to,vl;
};
struct node{
	int val,len,belong;
}map[200200];
vector<table> ve[200200];
int mm[10000100],cm[10000100];
int w[200200];
int ww[200200];
int fa[200200];
int size[200200];
bool biao[200200];
void dfs(int x)
{
	size[x]=0;
	for(int i=0;i<ve[x].size();i++)
	{
		table y=ve[x][i];
		if(y.to!=fa[x]&&!biao[y.to])
		{
			fa[y.to]=x;
			dfs(y.to);
			size[x]+=size[y.to];
		}
	}
	size[x]++;
}
void getroot(int x)
{
	int maxa=-1;
	for(int i=0;i<ve[x].size();i++)
	{
		table y=ve[x][i];
		if(y.to!=fa[x]&&!biao[y.to])
		{
			getroot(y.to);
			maxa=max(maxa,size[y.to]);
		}
	}
	maxa=max(maxa,m-size[x]);
	if(maxa<mina)
		mina=maxa,head=x;
}
void suan(int x,int now)
{
	for(int i=0;i<ve[x].size();i++)
	{
		table y=ve[x][i];
		if(y.to!=fa[x]&&!biao[y.to])
		{
			fa[y.to]=x,map[++tot].val=w[y.to]=w[x]+y.vl,map[tot].belong=now,map[tot].len=ww[y.to]=ww[x]+1;
			suan(y.to,now);
		}
	}
}
void fz(int x)
{
	fa[x]=x;
	dfs(x);
	m=size[x],mina=2147483647;
	getroot(x);
	int fuck=head;
	biao[fuck]=1;
	tot=0;
	map[++tot].val=0,map[tot].belong=0,map[tot].len=0;
	for(int i=0;i<ve[fuck].size();i++)
	{
		table y=ve[fuck][i];
		if(!biao[y.to])
		{
			fa[y.to]=fuck,map[++tot].val=w[y.to]=y.vl,map[tot].belong=i+1,map[tot].len=ww[y.to]=1;
			suan(y.to,i+1);
		}
	}
	for(int i=1;i<=tot;i++)
	{
		if(map[i].val>k) continue;
		int fi=mm[map[i].val],se=cm[map[i].val];
		if(fi==2147483647) mm[map[i].val]=i;
		else if(map[i].len<=map[fi].len)
		{
			if(map[i].belong==map[fi].belong)
			{
				mm[map[i].val]=i;
			}
			else
			{
				cm[map[i].val]=fi;
				mm[map[i].val]=i;
			}
		}
		else if((se==2147483647)&&(map[i].belong!=map[fi].belong)) cm[map[i].val]=i;
		else if(map[i].len<map[se].len)
		{
			if(map[i].belong!=map[fi].belong)
			{
				cm[map[i].val]=i;
			}
		}
	}
	for(int i=1;i<=tot;i++)
	{
		if(map[i].val>k) continue;
		int y=k-map[i].val;
		if(mm[y]!=2147483647)
		{
			if(map[mm[y]].belong!=map[i].belong) ans=min(ans,map[i].len+map[mm[y]].len);
			else if(cm[y]!=2147483647) ans=min(ans,map[i].len+map[cm[y]].len);
		}
	}
	for(int i=1;i<=tot;i++)
	{
		if(map[i].val>k) continue;
		mm[map[i].val]=cm[map[i].val]=2147483647;
	}
	for(int i=0;i<ve[fuck].size();i++)
	{
		table y=ve[fuck][i];
		if(!biao[y.to]) fz(y.to);
	}
}
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);
		ve[x].push_back((table){y,z});
		ve[y].push_back((table){x,z});
	}
	for(int i=0;i<=k+10;i++)
		mm[i]=cm[i]=2147483647;
	fz(0);
	if(ans==2147483647) cout<<"-1"<<endl;
	else cout<<ans<<endl;
	return 0;
}