P2491加强版过了,这题WA on #13
查看原帖
P2491加强版过了,这题WA on #13
945845
Chernobog_Belobog楼主2025/7/28 12:27
#include <bits/stdc++.h>
using namespace std;
#define int long long

int n , s , x , y , z , a , b , cnt , t , ans = 0x3f3f3f3f3f3f3f3f , dis[300007] , dis1[300007] , pre[300007] , ew[300007] , sum[300007] , que[300007];
struct node {
	int v , w;
};
vector <node> g[300007];
queue <int> q , qq;

void dfs(int u , int fa , int sum , bool flag) {
    if (flag) pre[u] = fa , ew[u] = sum;
    dis[u] = dis[fa] + sum;
    for (auto p : g[u]) if (p.v != fa) dfs(p.v , u , p.w , flag);
}

void bfs() {
    memset(dis , 0x3f , sizeof dis);
    for (int i = b ; i ; i = pre[i]) q.push(i) , qq.push(i) , dis[i] = 0;
    while (!q.empty()) {
        int u = q.front() , uu = qq.front(); q.pop() , qq.pop();
        for (auto p : g[u]) if (dis[p.v] == 0x3f3f3f3f3f3f3f3f) dis[p.v] = dis[u] + p.w , dis1[uu] = max(dis1[uu] , dis[p.v]) , q.push(p.v) , qq.push(uu);
    }
}

signed main () {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> s;
	for (int i = 1 ; i < n ; i++) {
		cin >> x >> y >> z;
		g[x].push_back((node){y , z}) , g[y].push_back((node){x , z});
	}
	dfs(1 , 0 , 0 , 0);
	for (int i = 1 , tmp = 0 ; i <= n ; i++) if (tmp < dis[i]) tmp = dis[i] , a = i;
	dfs(a , 0 , 0 , 1);
	for (int i = 1 , tmp = 0 ; i <= n ; i++) if (tmp < dis[i]) tmp = dis[i] , b = i;
	bfs();
	pre[n + 1] = b;
	for (int i = n + 1 ; i ; i = pre[i]) sum[pre[i]] = sum[i] + ew[i];
	for (int l = b , r = b ; l && r != a ; l = pre[l]) {
	    int last = r; cnt++;
	    while (sum[r] - sum[l] <= s && r != 0) {
	  	    last = r , r = pre[r];
	  	    if (r != 0 && sum[r] - sum[l] <= s) {
	  	        while (dis1[r] >= que[t] && t >= cnt) t--;
	  	        que[++t] = dis1[r];	
		    }
	    }
	    if (r == 0 || sum[r] - sum[l] > s) r = last;
	    int now = max(sum[l] , sum[a] - sum[r]);
	    now = max(now , que[cnt]) , ans = min(now , ans);
	}
	cout << ans;
	return 0;
}
2025/7/28 12:27
加载中...