P3761 [TJOI2017]城市(树形DP)

nofind · 2019-10-21 20:03:02 · 题解

题意:https://www.luogu.org/problem/P3761

前面两个直接树的直径,考最后一个

设h[x]表示x的连通块到x的最大距离,我们显然要连接u和v的连通块中h[]最小的两个

考虑h[x]的取值可能:

1.f[x]表示x的子树中最长链,这个在求直径时已经求出来了

2.假设z是x的父亲节点,z子树中除了包含x的子树的最长链+w(z,x)

3.假设z是x的父亲节点,除了z的子树外到z最长链+w(z,x)

在求直径时求出f[x]表示x的子树中最长链和g[x]x的子树中次长链,maxson[x]表示含有x的子树中最长链的x的儿子的位置,之后再dfs一遍即可

code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=5010;
int n,cnt=1,ans=453533453,tmp;
int head[maxn],f[maxn],g[maxn],maxson[maxn];
bool check[maxn<<1];
struct edge{int to,nxt,dis;}e[maxn<<1];
inline void add(int u,int v,int w){e[++cnt].nxt=head[u];head[u]=cnt;e[cnt].to=v;e[cnt].dis=w;}
void dfs1(int x,int fa)
{
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(y==fa||check[i])continue;
        dfs1(y,x);
        tmp=max(tmp,f[x]+f[y]+e[i].dis);
        if(f[y]+e[i].dis>f[x])g[x]=f[x],f[x]=f[y]+e[i].dis,maxson[x]=y;
        else if(f[y]+e[i].dis>g[x])g[x]=f[y]+e[i].dis;
    }
}
void dfs2(int x,int fa,int maxx)
{
    tmp=min(tmp,max(maxx,f[x]));
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(y==fa||check[i])continue;
        if(maxson[x]==y)dfs2(y,x,max(g[x]+e[i].dis,maxx+e[i].dis));
        else dfs2(y,x,max(f[x]+e[i].dis,maxx+e[i].dis));
    }
}
inline void init()
{
    memset(f,0,sizeof(f));
    memset(g,0,sizeof(g));
    memset(maxson,0,sizeof(maxson));
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);add(v,u,w);
    }
    for(int i=2;i<=cnt;i+=2)
    {
        init();
        int d1,d2,d3,d4,x=e[i].to,y=e[i^1].to;
        check[i]=check[i^1]=1;
        tmp=0,dfs1(x,0);d1=tmp;
        tmp=0,dfs1(y,0);d2=tmp;
        tmp=42342344,dfs2(x,0,0);d3=tmp;
        tmp=42342344,dfs2(y,0,0);d4=tmp;
        ans=min(ans,max(max(d1,d2),d3+d4+e[i].dis));
        check[i]=check[i^1]=0;
    }
    printf("%d",ans);
    return 0;
}