原題鏈接

解析

對于樹上任意一點(diǎn) \(u\)，任意直徑的兩個端點(diǎn)中至少有一個在離 \(u\) 距離最大的點(diǎn)的集合中。

我怎么把這個給忘了？

知道這個性質(zhì)后，就可以構(gòu)造操作讓每個點(diǎn)都取到最大值了
。具體地，先求出一條直徑，然后刪掉除該直徑端點(diǎn)以外的所有點(diǎn)，最后刪直徑，實(shí)現(xiàn)類似拓?fù)洹?/p>

代碼

/*
*/
#include<bits/stdc++.h>
#define eps 0.000001
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll,int> pii;
const int N = 2e5 + 5,M = 3.2e4 + 5;
vector<int> tr[N];
int dis1[N],dis2[N],du[N];
void dfs(int x,int fa,int *dis){
	dis[x] = dis[fa] + 1;
	for(int nx : tr[x])if(nx != fa){
		dfs(nx,x,dis);
	}
}
struct S{
	int a,b,c;
};
vector<S> res;
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out1.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		tr[u].push_back(v);
		tr[v].push_back(u);
		du[u]++,du[v]++;
	}
	dis1[0] = dis2[0] = -1;
	dfs(1,0,dis1); 
	int s = 1,t = 1;
	for(int i=1;i<=n;i++){
		if(dis1[i] > dis1[s]) s = i;
	}
	dfs(s,0,dis1);
	for(int i=1;i<=n;i++){
		if(dis1[i] > dis1[t]) t = i;
	}
	dfs(t,0,dis2);
	ll sum = 0;
	queue<int> q;
	for(int i=1;i<=n;i++)if(i != s && i != t){
		if(du[i] == 1) q.push(i);	
	}
	while(!q.empty()){
		int u = q.front();
		q.pop();
		if(dis1[u] > dis2[u]){
			res.push_back({s,u,u});
			sum += dis1[u];
		}else{
			res.push_back({t,u,u});
			sum += dis2[u];
		}
		for(int v : tr[u])if(du[v]){
			du[v]--,du[u]--;
			if(du[v] == 1){
				q.push(v);
			}
		}
	}
	int now = s;
	while(now != t){
		sum += dis2[now];
		res.push_back({now,t,now});
		for(int nxt : tr[now])if(du[nxt]){
			du[now]--;
			du[nxt]--;
			now = nxt;
			break;
		}
	}
	cout<<sum<<'\n';
	for(int i=0;i<=n - 2;i++){
		cout<<res[i].a<<" "<<res[i].b<<" "<<res[i].c<<'\n';
	}
	return 0;
}
/*
*/