link:https://codeforces.com/contest/911/problem/F
给一棵树,你需要进行若干次操作:选择两个叶子,把他们的距离加入得分,删掉其中一个叶子。希望让最终得分最大。构造方案。
删叶子,距离最大,考虑树的直径
很明显用树的直径不会让答案更劣(一棵树可能有多个直径,但直径的中心是唯一的,在此基础上考虑),因此找到直径后跑一次dfs,先把非直径的点删完,再删直径上的点。
// LUOGU_RID: 154445534
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=2e5+5;
int n,dep[N],fa[20][N];
int rt,c;
bool tag[N];
vector<vector<int>> G;
vector<tuple<int,int,int>> ans;
ll ret;
void dfs(int x){
for(auto to:G[x])if(to!=fa[0][x]){
dep[to]=dep[x]+1;
fa[0][to]=x;
if(dep[to]>dep[c])c=to;
dfs(to);
}
}
int jump(int x,int k){
int t=0;
for(;k;t++,k>>=1)if(k&1)x=fa[t][x];
return x;
}
int LCA(int a,int b){
if(dep[a]>dep[b])swap(a,b);
b=jump(b,dep[b]-dep[a]);
if(a==b)return a;
int i=18;
while(a!=b){
for(;i>=0;i--)if(fa[i][a]!=fa[i][b]){
a=fa[i][a];
b=fa[i][b];
}
if(i==-1)a=b=fa[0][a];
}
return a;
}
int dist(int a,int b){
return dep[a]+dep[b]-2*dep[LCA(a,b)];
}
void dfs2(int x){
for(auto to:G[x])if(to!=fa[0][x]&&!tag[to])dfs2(to);
for(auto to:G[x])if(to!=fa[0][x]&&tag[to])dfs2(to);
if(x!=rt){
if(tag[x]){
ret+=dep[x]-dep[rt];
ans.push_back({x,rt,x});
}else{
int D1=dist(x,rt),D2=dist(x,c);
if(D1>D2){
ret+=D1;
ans.push_back({x,rt,x});
}else{
ret+=D2;
ans.push_back({x,c,x});
}
}
}
}
int main(){
fastio;
cin>>n;
G=vector<vector<int>>(n+1);
rep(i,1,n-1){
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1);
dep[rt=c]=0;
rep(i,1,n)fa[0][i]=0;
dfs(c);
//diameter will be rt->c
rep(j,1,18)rep(i,1,n)fa[j][i]=fa[j-1][fa[j-1][i]];
int x=c;
while(x!=rt){
tag[x]=true;
x=fa[0][x];
}
dfs2(rt);
cout<<ret<<endl;
for(auto [x,y,c]:ans)cout<<x<<' '<<y<<' '<<c<<endl;
return 0;
}
标签:rt,dep,CF911F,int,back,构造,fa,直径
From: https://www.cnblogs.com/yoshinow2001/p/18124322