P3761 [TJOI2017]城市
这道题做了一晚上。
好题。
一句话题意：给你一棵树，让你可以去掉一条边，再在别的位置上加上一条边权相等的边，使得这个图还是一棵树，并且在这棵树的前提下，相距最远的两个点的距离最小。
首先很容易知道我们要换的边一定在原树的直径上，反证法。
所以求出树的直径打上标记，然后枚举拆去哪一条边就行了。
我们拆去一条边之后，原来的树会变成两棵新树，我们可以将这两棵新树任意合并，要求的是合并之后的新树的直径。
可以分成三种情况：首先有可能是两颗小树的直径之一。
第三种情况是当我们把这两棵树的重心连在一起之后，新树的直径：也就是原来两棵子树中以重心为根的前提下的最长链之和加上我们当前拆的这条边的边权。
前两种比较好求，直接还是按照求直径的方法来就行，注意区分两棵子树。
第三种的话，我们需要求出当前树的重心和到重心的最长链。
怎么求？这里用到了换根DP，这也是合并树求直径的常用套路。
首先我们设\(f[u]\)表示以u为根的子树中，到u的最长链，那么枚举子节点，先将当前枚举到的子节点DP出来，然后转移即可。转移方程：\(f(u)=max(f(u),f(v)+edge(i).dis)\)
同时，还需要维护一个次长链，后面有用，跟着f转移就行。
类似点分治求重心的思想，我们可以发现对于u，还有他上面的一条链没有算，这个时候就要进行换根，所以我们的第二遍DP是进行换根，求出以u为根的全局最长链，XJB转移一下就可以了。
code：
#include <iostream>
#include <cstdio>
#include <cstring>
//#define int long long
using namespace std;
const int wx=5017;
inline int read(){
int sum=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0';ch=getchar();}
return sum*f;
}
int totx,toty,num,n,m,pos,tmp,root,maxx,maxy,ans=2147483642;
int head[wx],dis[wx],vis[wx],visx[wx],visy[wx],flag[wx];
int f[wx],size[wx],g[wx],ff[wx],gg[wx];
struct e{
int nxt,to,dis;
}edge[wx*2];
void add(int from,int to,int dis){
edge[++num].nxt=head[from];
edge[num].to=to;
edge[num].dis=dis;
head[from]=num;
}
void dfs_1(int u,int fa){
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa)continue;
dis[v]=dis[u]+edge[i].dis;
dfs_1(v,u);
}
}
void dfs_2(int u,int fa){
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa)continue;
dis[v]=dis[u]+edge[i].dis;
dfs_2(v,u);
}
}
bool dfs_3(int u,int fa){
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa)continue;
if(dfs_3(v,u)||v==pos){
flag[i]=1;
return true;
}
}
return false;
}
void init(){
n=read();
for(int i=1;i<n;i++){
int x,y,z;
x=read(); y=read(); z=read();
add(x,y,z); add(y,x,z);
}
}
void find_length(){
dfs_1(1,0);
for(int i=1;i<=n;i++){
if(dis[i]>tmp){
root=i;
tmp=dis[i];
}
}
memset(dis,0,sizeof dis);
dfs_2(root,0);
tmp=0;
for(int i=1;i<=n;i++){
if(dis[i]>tmp){
pos=i;
tmp=dis[i];
}
}
dfs_3(root,0);//起点root，终点pos
}
void dfs_5(int u,int fa){
visx[u]=1;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa||visy[u])continue;
dis[v]=dis[u]+edge[i].dis;
totx+=edge[i].dis;
dfs_5(v,u);
}
}
void dfs_6(int u,int fa){
visy[u]=1;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa||visx[u])continue;
dis[v]=dis[u]+edge[i].dis;
toty+=edge[i].dis;
dfs_6(v,u);
}
}
void dfs_7(int u){
vis[u]=1;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(!visx[v]||vis[v])continue;
dis[v]=dis[u]+edge[i].dis;
dfs_7(v);
}
}
void dfs_8(int u){
vis[u]=1;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(!visy[v]||vis[v])continue;
dis[v]=dis[u]+edge[i].dis;
dfs_8(v);
}
}
void dp_1(int u,int fa){
vis[u]=1;
f[u]=g[u]=0;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(vis[v]||v==fa)continue;
dp_1(v,u);
if(f[u]<f[v]+edge[i].dis){
g[u]=f[u];
f[u]=f[v]+edge[i].dis;
}
else if(g[u]<f[v]+edge[i].dis){
g[u]=f[v]+edge[i].dis;
}
}
vis[u]=0;
}
int dfs2(int u,int fa){
vis[u]=1;
int re=f[u],w;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(vis[v]||v==fa)continue;
if(f[u]==f[v]+edge[i].dis){
w=edge[i].dis+g[u];
}
else w=edge[i].dis+f[u];
if(w>=f[v]){
g[v]=f[v];f[v]=w;
}
else if(w>g[v]){
g[v]=w;
}
re=min(re,dfs2(v,u));
}
vis[u]=0;
return re;
}
void find_ans(int x,int y,int now){
memset(visx,0,sizeof visx);
memset(visy,0,sizeof visy);
memset(dis,0,sizeof dis);
memset(vis,0,sizeof vis);
// cout<<x<<"zz"<<y<<endl;
int re=0;
dp_1(x,y);re=dfs2(x,y);
dp_1(y,x);re+=dfs2(y,x)+now;
totx=0; toty=0;
dfs_5(x,y); dfs_6(y,x);//将所有点划分到x和y的两个集合内 //接下来去找两棵子树中的重心
int tmpx=0,tmpy=0;
int rootx=0,rooty=0;
for(int i=1;i<=n;i++){
if(visx[i]){
if(tmpx<dis[i]){
tmpx=dis[i];
rootx=i;
}
}
if(visy[i]){
if(tmpy<dis[i]){
tmpy=dis[i];
rooty=i;
}
}
}
memset(dis,0,sizeof dis);
memset(vis,0,sizeof vis);
dfs_7(rootx); dfs_8(rooty);
int zmjx=0,zmjy=0;
for(int i=1;i<=n;i++){
if(visx[i]){
zmjx=max(zmjx,dis[i]);
}
else zmjy=max(zmjy,dis[i]);
}
re=max(re,max(zmjx,zmjy));
ans=min(ans,re);
}
void dfs_4(int u,int fa){
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa||!flag[i])continue;
find_ans(u,v,edge[i].dis);
dfs_4(v,u);
}
}
void work(){
dfs_4(root,0);
printf("%d\n",ans);
}
signed main(){
init();
find_length();
work();
return 0;
}