树
Link Cut Centroids
思路：树的重心，判断一个重心和两个重心的情况。当存在两个重心时，两个重心必相邻。只需把其中一个重心的边连在另一个重心上即可。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
const int maxn = 1e5+10;
int n;
int sz[maxn];
int sum[maxn];
int fa[maxn];
int r1,r2;
int mx=1e9;
vector <int > g[maxn];
void dfs(int u,int f)
{
sz[u]=1;
sum[u]=0;
for(auto v:g[u])
{
if(v==f) continue;
dfs(v,u);
sz[u]+=sz[v];
sum[u]=max(sum[u],sz[v]);
}
sum[u]=max(sum[u],n-sz[u]);
if(sum[u]==mx)
{
r2=u;
}
if(sum[u]<mx)
{
r1=u;
r2=0;
mx=sum[u];
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)
{
r1=r2=0;
cin>>n;
for(int i=0;i<=n;i++)
{
mx=1e9;
sz[i]=sum[i]=fa[i]=0;
g[i].clear();
}
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1,-1);
if(!r2)
{
int u=r1;
int v=g[u][0];
cout<<u<<" "<<v<<endl;
cout<<u<<" "<<v<<endl;
}
else
{
int v;
for(int i=0;i<g[r2].size();i++)
{
if(g[r2][i]!=r1)
{
v=g[r2][i];
break;
}
}
cout<<r2<<" "<<v<<endl;
cout<<r1<<" "<<v<<endl;
}
}
}
核心城市
P5536 【XR-3】核心城市 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路：显然求与核心城市的距离最大的城市，其与核心城市的距离最小那么k座城市一定在树的直径上。然后我们以这个直径的中点为根，把其他节点按照以这个节点为根的子树中节点的最大深度-这个点的深度排序选前$k−1$个节点即可
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
const int maxn = 1e5+10;
int n,k;
int c;
int r1,r2;
int d[maxn];
int md[maxn];
int fa[maxn];
int ans[maxn];
vector <int > g[maxn];
vector <int > path;
void dfs(int u,int f)
{
for(auto v:g[u])
{
if(v==f) continue;
d[v]=d[u]+1;
fa[v]=u;
if(d[v]>d[c]) c=v;
dfs(v,u);
}
}
void dfs1(int u,int f)
{
md[u]=d[u];
for(auto v:g[u])
{
if(v==f) continue;
d[v]=d[u]+1;
dfs1(v,u);
md[u]=max(md[u],md[v]);
}
}
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1,-1);
r1=c;
d[c]=0,dfs(c,-1);
r2=c;
for(int i=1;i<=(d[c]+1)/2;i++) r2=fa[r2];
d[r2]=0;
dfs1(r2,-1);
for(int i=1;i<=n;i++) ans[i]=md[i]-d[i];
sort(ans+1,ans+1+n,cmp);
int sum=0;
for(int i=k+1;i<=n;i++) sum=max(sum,ans[i]+1);
cout<<sum<<endl;
}
Three Paths on a Tree
思路：首先这三个点中其中两个点一定是这棵树直径的端点，其次在直径外找一点离两个端点距离最远即可
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
const int maxn = 2e5+10;
vector <int > g[maxn];
int n,c;
int d[maxn];
int d1[maxn];
int d2[maxn];
int fa[maxn];
int vis[maxn];
int ans3;
int ans=0;
void dfs(int u,int f)
{
for(auto v:g[u])
{
if(v==f) continue;
d[v]=d[u]+1;
fa[v]=u;
if(d[v]>d[c]) c=v;
dfs(v,u);
}
return ;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1,-1);
int ans1=c;
d[c]=0,dfs(c,-1);
int ans2=c;
for(int i=1;i<=n;i++) d1[i]=d[i];
d[ans2]=0;
dfs(ans2,-1);
for(int i=1;i<=n;i++) d2[i]=d[i];
for(int i=1;i<=n;i++)
{
if(i==ans1||i==ans2) continue;
if(d1[i]+d2[i]>d1[ans3]+d2[ans3]) ans3=i;
}
ans=d1[ans3]+d2[ans3]+d1[ans2];
ans/=2;
cout<<ans<<endl;
cout<<ans1<<" "<<ans2<<" "<<ans3<<endl;
}
逃学的小孩
[P4408 NOI2003] 逃学的小孩 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路：既然要要求耗时最长，那么就假定AB两点恰好为该树直径的端点，然后遍历找耗时最大的点即可
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
const int maxn = 2e5+10;
typedef long long ll;
struct edge{
int v,w,net;
}e[maxn*2];
int head[maxn];
int cnt;
int n,m;
int r1,r2;
int c;
ll d[maxn];
ll d1[maxn];
ll d2[maxn];
int fa[maxn];
void add(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].net=head[u];
head[u]=cnt;
}
void dfs(int u,int ff)
{
for(int i=head[u];i;i=e[i].net)
{
int v=e[i].v;
if(v==ff) continue;
d[v]=d[u]+e[i].w;
if(d[v]>d[c]) c=v;
dfs(v,u);
}
return ;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<n;i++)
{
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
dfs(1,-1);
r1=c;d[c]=0;
dfs(c,-1);
r2=c;
for(int i=1;i<=n;i++) d1[i]=d[i];
d[c]=0;
dfs(c,-1);
for(int i=1;i<=n;i++) d2[i]=d[i];
ll ans=0;
for(int i=1;i<=n;i++)
{
ans=max(min(d1[i],d2[i])+d1[r2],ans);
}
cout<<ans<<endl;
}
树网的核
[P1099 NOIP2007 提高组] 树网的核 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路：先找出该树的直径，对该直径进行尺取，计算每条路径的偏心距，取最大值
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <deque>
using namespace std;
const int maxn = 310;
struct edge{
int v,w,net;
}e[maxn*2];
int head[maxn];
int d[maxn];
int fa[maxn];
int vis[maxn];
int q[maxn];
int c,n,s;
int cnt;
void add(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].net=head[u];
head[u]=cnt;
}
void dfs(int u,int ff)
{
for(int i=head[u];i;i=e[i].net)
{
int v=e[i].v;
if(v==ff||vis[v]) continue;
fa[v]=u;
d[v]=d[u]+e[i].w;
if(d[v]>d[c]) c=v;
dfs(v,u);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>s;
vector <int > path(n+1);
for(int i=1;i<n;i++)
{
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
dfs(1,-1);
d[c]=0,fa[c]=0;dfs(c,-1);
int r=c;
int ans=1e9;
for(int i=c,j=c;i;i=fa[i])
{
while(d[j]-d[i]>s) j=fa[j];
int x=max(d[c]-d[j],d[i]);
ans=min(ans,x);
}
for(int i=r;i;i=fa[i]) vis[i]=1;
for(int i=r;i;i=fa[i])
{
c=i;
d[i]=0;
dfs(i,fa[i]);
}
for(int i=1;i<=n;i++) ans=max(ans,d[i]);
cout<<ans<<endl;
}
巡逻
思路：题目意思大致是构建一个或两个环，在一颗树中从一个点开始遍历所有点并返回的代价为$2(n-1)$。当$k=1$时，只要将该树的直径两个端点链接便可的到最小值$2(n-1)-d1+1$。当$k=2$，在$k=1$的操作下，找到除了直接$d1$外最长的边即可。只要将直径$d1$上的所有边权改为-1，然后用树上dp就直径，最后答案为$2*(n-1)-d1+1-d2+1$.
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
const int maxn = 1e5+10;
struct node{
int v,w,net;
}e[2*maxn];
int head[maxn];
int tot;
int c;
int r1,r2;
int d[maxn];
int vis[maxn];
int d1[maxn],d2[maxn];
int ans;
int fa[maxn];
int fe[maxn];
void add(int u,int v,int w)
{
e[++tot].v=v;
e[tot].w=w;
e[tot].net=head[u];
head[u]=tot;
}
void dfs(int u,int ff)
{
for(int i=head[u];i;i=e[i].net)
{
int v=e[i].v;
if(v==ff||vis[v]) continue;
vis[v]=1;
fa[v]=u;
fe[v]=i;
d[v]=d[u]+e[i].w;
if(d[v]>d[c]) c=v;
dfs(v,u);
}
}
void dfs1(int u,int ff)
{
d1[u]=0,d2[u]=0;
for(int i=head[u];i;i=e[i].net)
{
int v=e[i].v;
if(v==ff||vis[v]) continue;;
vis[v]=1;
dfs1(v,u);
int t=d1[v]+e[i].w;
if(t>d1[u])
{
d2[u]=d1[u];
d1[u]=t;
}
else if(t>d2[u])
{
d2[u]=t;
}
}
ans=max(ans,d1[u]+d2[u]);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n,k;
cin>>n>>k;
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
add(x,y,1);
add(y,x,1);
}
dfs(1,-1);
d[c]=0,r1=c,fa[c]=0;
memset(vis,0,sizeof vis);
dfs(c,-1);
r2=c;
if(k==1)
{
int s=2*(n-1)-d[c]+1;
cout<<s<<endl;
return 0;
}
for(int i=r2;i!=r1;i=fa[i])
{
int id=fe[i];
e[id].w=-1;
e[id+((id&1)?1:-1)].w=-1;
}
fa[1]=0;
memset(vis,0,sizeof vis);
dfs1(1,-1);
int s=0;
s=2*(n-1)-d[c]+1-ans+1;
cout<<s<<endl;
}
HXY造公园
P2195 HXY造公园 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路：对于问题一，直接dfs找直径即可。对于问题二，用并查集维护连通块，若不在同一个连通快上，则新形成的连通快的直径为$dis[fy]=max(max((dis[fx]+1)/2+(dis[fy]+1)/2+1,dis[fy]),dis[fx]);$
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 3e5+10;
vector <int > g[maxn];
int n,m,q;
int s=0;
int v=-1;
int dis[maxn];
int fa[maxn];
int vis[maxn];
int c;
int find(int x)
{
return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
int fx=find(x);
int fy=find(y);
if(fx==fy) return ;
fa[fx]=fy;
}
void dfs(int u,int f,int d)
{
if(d>v) v=d,c=u;
for(auto v:g[u])
{
if(v==f) continue;
dfs(v,u,d+1);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
merge(x,y);
}
for(int i=1;i<=n;i++)
{
if(fa[i]!=i) continue;
v=-1;
dfs(i,-1,0);
v=-1;
dfs(c,-1,0);
dis[i]=v;
}
while(q--)
{
int op;
cin>>op;
if(op==1)
{
int x;
cin>>x;
cout<<dis[find(x)]<<endl;
}
else
{
int x,y;
cin>>x>>y;
int fx=find(x);
int fy=find(y);
if(fx==fy) continue;
dis[fy]=max(max((dis[fx]+1)/2+(dis[fy]+1)/2+1,dis[fy]),dis[fx]);
merge(x,y);
}
}
return 0;
}
直径
思路：先找到该树的直径，并记录路径上的点，然后从路径上每一个点再次dfs，然后从每个点再次DFS
显然如果从某个点出发，能找到第二条与当前一边直径长度相等的一条路径，那么这条边就为可行边
分别从左右出发找一下即可。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
struct edge{
int v;
ll w;
int net;
}e[maxn*2];
int head[maxn];
ll sum[maxn];
ll val[maxn];
int arr[maxn];
int vis[maxn];
int tot;
int fa[maxn];
int c,r1,r2;
ll d[maxn];
void add(int u,int v,ll w)
{
e[++tot].v=v;
e[tot].w=w;
e[tot].net=head[u];
head[u]=tot;
}
void dfs(int u,int ff)
{
for(int i=head[u];i;i=e[i].net)
{
int v=e[i].v;
if(v==ff||vis[v]) continue;
d[v]=d[u]+e[i].w;
fa[v]=u;
if(d[v]>d[c]) c=v;
dfs(v,u);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
for(int i=1;i<n;i++)
{
int u,v; ll w;
cin>>u>>v>>w;
add(u,v,w);add(v,u,w);
}
dfs(1,-1);
d[c]=0,fa[c]=0,r1=c;
dfs(c,-1);
r2=c;
int cnt=0;
for(int i=r2;i;i=fa[i])
{
vis[i]=1;
arr[++cnt]=i;
}
reverse(arr+1,arr+1+cnt);
for(int i=1;i<=cnt;i++)
{
sum[i]=d[arr[i]];
}
for(int i=1;i<=cnt;i++)
{
d[arr[i]]=0;
c=arr[i];
dfs(arr[i],-1);
val[i]=d[c];
}
int l=1,r=cnt;
for(int i=1;i<=cnt;i++)
{
if(val[i]==sum[i]) l=i;
}
for(int i=cnt;i>=1;i--)
{
if(val[i]==sum[cnt]-sum[i]) r=i;
}
cout<<sum[cnt]<<endl<<r-l<<endl;
}