meepo's Blog

Description

Input

Output

Sample Input

Sample Output

HINT

Source

    我的第3道点分模板。。。对于每一个点记录他到当前根的距离和经过的边数。。然后与不在同一子树中的点合并。。。

    我因为偷懒用了map导致跑得奇慢无比。。。差点以为过不去了。。

#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
struct data{int x,y,s,next;} e[N<<1];
struct node{int x,y;} DT[N];
int head[N],vis[N],f[N],son[N],d[N],root,tot,sum,n,K,x,y,s,cnt,ans;
map <int,int> hash;
int read(){
	int x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
void Insert(int x,int y,int s){
	e[++cnt].x = x;e[cnt].y = y;e[cnt].s = s;
	e[cnt].next = head[x];head[x] = cnt;
}
void getroot(int x,int fa){
	son[x] = 1;f[x] = 0;
	for (int i=head[x];i;i=e[i].next)
		if (e[i].y!=fa && !vis[e[i].y]){
			getroot(e[i].y,x);
			son[x]+=son[e[i].y];
			f[x] = max(f[x],son[e[i].y]);
		}
	f[x] = max(f[x],sum-son[x]);
	if (f[x]<f[root]) root = x;
}
void getdeep(int x,int fa,int dp){
	if (hash[K-d[x]]) ans = min(ans,dp+hash[K-d[x]]);
	if (K==d[x]) ans = min(ans,dp);
	DT[++tot] = (node){d[x],dp};
	for (int i=head[x];i;i=e[i].next)
		if (!vis[e[i].y] && e[i].y!=fa){
			d[e[i].y]  = d[x]+e[i].s;
			getdeep(e[i].y,x,dp+1);
		}
}
int calc(int x){
	hash.clear();
	for (int i=head[x];i;i=e[i].next)
		if (!vis[e[i].y]){
			tot = 0;
			d[e[i].y] = e[i].s;
			getdeep(e[i].y,x,1);
			for (int j=1;j<=tot;j++) 
				if (hash[DT[j].x]) hash[DT[j].x] = min(hash[DT[j].x],DT[j].y);
				else hash[DT[j].x] = DT[j].y;
		}
}
void work(int x){
	calc(x);
	vis[x] = 1;
	for (int i=head[x];i;i=e[i].next)
		if (!vis[e[i].y]){
			sum = son[e[i].y];root = 0;
			getroot(e[i].y,-1);
			work(root);
		}
}
int main(){
	n = read();K = read();
	for (int i=1;i<n;i++){
		x = read();y = read();s = read();
		Insert(x+1,y+1,s);Insert(y+1,x+1,s);
	}
	sum = n;ans = f[0] = 1e9;
	getroot(1,-1);
	work(root);
	if (ans!=1e9) printf("%d",ans);
	else printf("-1");
}