萌新袜子 86pts 球条
查看原帖
萌新袜子 86pts 球条
759710
LuoFeng_Nanami楼主2023/11/26 20:01

rt.

#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define F(i,a,b) for(rll i=a;i<=b;i++)
#define Fdn(i,a,b) for(rll i=a;i>=b;i--)
#define int ll

using namespace std;

const int inf = 0x3f3f3f3f,mod = 1e9 + 7; 
const int maxn = 300 + 7;

struct edge{
	int to, nxt, w;
}G[2 * maxn];

int tot;
int head[maxn];

inline void add(int u, int v, int w){ G[++tot].nxt = head[u], G[tot].to = v, G[tot].w = w, head[u] = tot; }

int n, s;
int fa[maxn];
int d[maxn];
int dia[maxn];
int beg, t;
int yousa;
int dis[maxn];
int len[maxn][maxn];
int dia_dis[maxn];
map<int, bool> m;
int ans = inf, maxway;

inline void dfs_dia(int u, int f){
	fa[u] = f;
	for(int i = head[u]; i; i = G[i].nxt){
		int v = G[i].to, w = G[i].w;
		if(v == f) continue;
		d[v] = d[u] + w;
		if(d[v] > d[t]) t = v;
		dfs_dia(v, u);
	}
}

inline void dfs(int u, int f){
	for(int i = head[u]; i; i = G[i].nxt){
		int v = G[i].to, w = G[i].w;
		if(v == f || m[v]) continue;
		d[v] = d[u] + w;
		if(d[v] > d[yousa]) yousa = v;
		dfs(v, u);
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	cin >> n >> s;
	F(i, 1, n - 1){
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w), add(v, u, w);
		len[u][v] = len[v][u] = w;
	}
	dfs_dia(1, 0);
	d[t] = 0, beg = t;
	dfs_dia(t, 0);
	int tmp = t, cnt = 1; dia[cnt] = t, m[t] = 1, dia_dis[1] = len[t][fa[t]];
	while(tmp = fa[tmp])
		dia[++cnt] = tmp, m[tmp] = 1, dia_dis[cnt] = dia_dis[cnt - 1] + len[tmp][fa[tmp]];
//	F(i, 1, cnt) cout << dia[i] << " " << dia_dis[i] << "\n";
	F(i, 1, cnt){
		d[dia[i]] = d[yousa] = 0; dfs(dia[i], 0);
		dis[i] = d[yousa], maxway = max(maxway, dis[i]);
//		cout << dia[i] << " "<< dis[i] << "\n";
	}
	F(i, 1, cnt){
		for(int j = i + 1; dia_dis[j - 1] - dia_dis[i - 1] <= s && j <= cnt; j++){
//			cout << i << " " << j << "xls ak IOI";
			int ret = max(maxway, max(dia_dis[i - 1], dia_dis[cnt - 1] - dia_dis[j - 1]));
			ans = min(ans, ret);
//			cout << ret << " " << ans << "\n";
		}
			
	}
	cout << ans << endl;
	
	return 0;
}

2023/11/26 20:01
加载中...