树的中心
当选取树上节点 \(u\) 为根时，最长链最短，则称 \(u\) 为树的中心。
-
性质一：至多 \(2\) 个且一定相邻。
-
性质二：一定位于树的直径上。
-
性质三：若一棵树有多条直径，则它们必定交于树的中心。
-
性质四：树的中心为根时，根到直径两端点分别为最长 / 次长链。
U392706
板子。
code
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n;
struct E{
int v,w;
};
vector<E> G[N];
vector<int> ans;
int len1[N],len2[N],up[N];
void dfsd(int cur,int fa){
for(auto i:G[cur]){
if(i.v==fa) continue;
dfsd(i.v,cur);
if(len1[i.v]+i.w>len1[cur])
len2[cur]=len1[cur],
len1[cur]=len1[i.v]+i.w;
else if(len1[i.v]+i.w>len2[cur])
len2[cur]=len1[i.v]+i.w;
}
}
void dfsu(int cur,int fa){
for(auto i:G[cur]){
if(i.v==fa) continue;
up[i.v]=up[cur]+i.w;
if(len1[i.v]+i.w!=len1[cur])
up[i.v]=max(up[i.v],len1[cur]+i.w);
else
up[i.v]=max(up[i.v],len2[cur]+i.w);
dfsu(i.v,cur);
}
}
int main(){
cin>>n;
for(int i=1,u,v,w;i<n;i++)
cin>>u>>v>>w,
G[u].push_back({v,w}),
G[v].push_back({u,w});
dfsd(1,0),dfsu(1,0);
int mini=1e9;
for(int i=1;i<=n;i++){
if(mini>max(len1[i],up[i]))
mini=max(len1[i],up[i]),ans.clear(),ans.push_back(i);
else if(mini==max(len1[i],up[i]))
ans.push_back(i);
}
sort(ans.begin(),ans.end());
for(int i:ans) cout<<i<<'\n';
return 0;
}
CF1294F
显然三个点选两个树的直径上的点 \(u,v\) 更优。
至于第三个点 \(w\)，我们可以认为 \(w\) 一定会与 \(u \to v\) 的路径交于 \(lca(w,v)\)。
于是枚举 \(w\) 求 LCA 并取最大即可，\(O(n \log n)\)。
当然更简单而高效的方法就是以 \(u \to v\) 上的点进行多起点 BFS 求最长路即可，\(O(n)\)。
这里提供的实现是法二。
code
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n;
int x,y,dis,pre[N];
int z,ans;
vector<int> G[N<<1];
bool vis[N];
struct Edge{ int u,sum; };
void dfs(int cur,int sum){
if(sum>=dis) dis=sum,y=cur;
for(int i:G[cur])
if(i!=pre[cur])
pre[i]=cur,dfs(i,sum+1);
}
void bfs(){
queue<Edge> q;
int now=y; //z=pre[y];
while(now)
q.push({now,0}),vis[now]=1,now=pre[now];
while(!q.empty()){
Edge cur=q.front(); q.pop();
if(cur.sum>=ans&&cur.u!=x&&cur.u!=y) ans=cur.sum,z=cur.u;
for(int i:G[cur.u])
if(!vis[i])
q.push({i,cur.sum+1}),vis[i]=1;
}
}
int main(){
cin>>n;
for(int i=1,u,v;i<n;i++)
cin>>u>>v,
G[u].push_back(v),
G[v].push_back(u);
pre[1]=0,dfs(1,0);
x=y,pre[x]=0,dfs(x,0);
bfs();
cout<<dis+ans<<'\n'<<x<<' '<<y<<' '<<z;
return 0;
}
AT_agc001_c
反向思考，我们要求最少删除的点数，即是求最多保留的点数。
于是我们对于 \(k\) 进行奇偶性分讨，从而构造直径为 \(k\) 的树，在所有这些里面取保留点数最多的即可。
code
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int n,k,tot,ans;
vector<int> G[N<<1];
void dfs(int cur,int fa,int sum){
tot++;
if(sum==k/2) return;
for(int i:G[cur])
if(i!=fa)
dfs(i,cur,sum+1);
}
int main(){
cin>>n>>k;
for(int i=1,u,v;i<n;i++)
cin>>u>>v,
G[u].push_back(v),
G[v].push_back(u);
if(k%2==0)
for(int i=1;i<=n;i++)
tot=0,dfs(i,0,0),ans=max(ans,tot);
else
for(int i=1;i<=n;i++)
for(int j:G[i])
tot=0,dfs(i,j,0),dfs(j,i,0),ans=max(ans,tot);
cout<<n-ans;
return 0;
}