Subtask TLE求调
查看原帖
Subtask TLE求调
719405
Harry20111022楼主2024/11/20 22:18
#include<bits/stdc++.h>
using namespace std;

struct node{
	int k,dis;
};
int n,s,ma,u,root1,root2,dia[300010],last[300010],nex[300010],top,len;
bool f[300010],f1[300010];
vector<node> v[300010];

int read() {
  int x = 0, w = 1;
  char ch = 0;
  while (!isdigit(ch)) {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x * w;
}
void write(int x){
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}

void dfs(int k,int dis,int m){
	f[k] = true;
	if(dis > ma){
		ma = dis;
		u = k;
	}
	for(int i = 0;i < v[k].size();i++){
		node now = v[k][i];
		if(!f[now.k] && !f1[now.k]){
			dfs(now.k,dis + now.dis,k);
		}
	}
}

void dfs1(int k,int dis,int m){
	f[k] = true;
	dia[k] = dis;
	last[k] = m;
	if(dis > ma){
		ma = dis;
		u = k;
	}
	for(int i = 0;i < v[k].size();i++){
		node now = v[k][i];
		if(!f[now.k]){
			dfs1(now.k,dis + now.dis,k);
		}
	}
}

bool check(int mid){
	int l = root1,r = root2;
	while(l != root2 && dia[nex[l]] <= mid){
		l = nex[l];
	}
	while(r != root1 && dia[root2] - dia[last[r]] <= mid){
		r = last[r];
	}
	return dia[r] - dia[l] <= s;
}

int main(){
//	scanf("%d%d",&n,&s);
	n = read();
	s = read();
	
	for(int i = 1;i <= n - 1;i++){
		int a,b,c;
//		scanf("%d%d%d",&a,&b,&c);
		a = read();
		b = read();
		c = read();
//		cin >> a >> b >> c;
		v[a].push_back({b,c});
		v[b].push_back({a,c});
	}
	
	memset(f,0,sizeof(f));
	ma = -1;
	dfs(1,0,0);
	root1 = u;
	memset(f,0,sizeof(f));
	ma = -1;
	dfs1(root1,0,0);
	root2 = u;
	len = ma;
	int superwhen = root2;
	f1[root2] = true;
//	for(int i = last[root2];i != 0;i = last[i]){
//		nex[i] = superwhen;
//		superwhen = i;
//		f1[i] = true;
//	}
//	for(int i = root1;i != 0;i = nex[i]){
//		memset(f,0,sizeof(f));
//		ma = -1;
//		dfs(i,0,0);
//		top = max(top,ma);
//	}
	for(int i = last[root2];i != 0;i = last[i]){
		nex[i] = superwhen;
		superwhen = i;
		f1[i] = true;
		f1[last[i]] = true;
		memset(f,0,sizeof(f));
		ma = -1;
		dfs(i,0,0);
		top = max(top,ma);
	}
	if(len <= s){
		cout << top << endl;
		return 0;
	}
	int l = top,r = len;
	while(l < r){
		int mid = (l + r) >> 1;
		if(check(mid)){
			r = mid;
		}else{
			l = mid + 1;
		}
	}
//	cout << "last:";
//	for(int i = 1;i <= n;i++){
//		cout << last[i] << " ";
//	}
//	cout << endl << "next:";
//	for(int i = 1;i <= n;i++){
//		cout << nex[i] << " ";
//	}
//	cout << endl << "dia:";
//	for(int i = 1;i <= n;i++){
//		cout << dia[i] << " ";
//	}
//	cout << endl << "dp:";
//	for(int i = 1;i <= n;i++){
//		cout << dp[i] << " ";
//	}
//	cout << endl;
//	cout << len << " " << top << " " << root1 << " " << root2 << endl;
	
//	printf("%d",r);
	write(r);
	
	return 0;
}
2024/11/20 22:18
加载中...