40pts 求调
查看原帖
40pts 求调
669825
SpringFullGarden楼主2024/1/20 21:26

RT

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ui unsigned int
using namespace std;

inline int rd() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

vector <pair <int, int> > e[200005];
int d[200005], fa[200005], dep[200005], vis[200005];
int n, top, root, lst, l, r;

void dfs1(int x) {
	for(auto it : e[x]) {
		int v = it.first, w = it.second;
		if(v == fa[x]) continue;
		fa[v] = x;
		d[v] = d[x] + w;
		dep[v] = dep[x] + 1;
		if(d[v] > d[lst]) lst = v;
		dfs1(v);
	}
}
void dfs2(int x, int fath) {
	if(d[x] == d[lst]) r = min(r, dep[fath]);
	if(d[x] == 2 * d[fath]) l = max(l, dep[fath]);
	for(auto it : e[x]) {
		int v = it.first;
		if(v == fa[x] || vis[v]) continue;
		dfs2(v, fath);
	}
}
int main() {
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
	n = rd();
	for(int i = 1; i < n; i++) {
		int u = rd(), v = rd(), w = rd();
		e[u].push_back(make_pair(v, w));
		e[v].push_back(make_pair(u, w));
	}
	dfs1(1); root = lst;
	fa[root] = d[root] = dep[root] = 0, dfs1(root);
	for(int i = lst; i; i = fa[i]) ++top, vis[i] = 1;
	l = 0, r = top;
	for(int i = lst; i; i = fa[i]) dfs2(i, i);
	cout << d[lst] << '\n' << r - l;
    return 0;
}
2024/1/20 21:26
加载中...