HDU 5886 Tower Defence

树的直径。

比赛的时候想着先树$dp$处理子树上的最长链和次长链，然后再从上到下进行一次$dfs$统计答案，和$CCPC$网络赛那个树$dp$一样，肯定是可以写的，但会很烦.......后来写崩了。

然后有一种新思路，很容易写。

假设下图中红线是树的直径，圆圈是直径上的节点，黑线表示一颗树。

如果删除的边不在直径上，那么删除这条边的答案就是直径长度。

如果删除的边在直径上，也就把下面的图分成了两半，左边和右边。

左边最大值会在什么情况下产生？

必然是$A->B->C$这样的情况产生的。不可能是从$D$到$C$这样的路径产生，因为$D->E$的长度最长只可能是$A->D$的长度。

右边部分最大值产生的情况也是一样的。

所以只要递推一下就可以了。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-6;
void File()
{
    freopen("D:\in.txt","r",stdin);
    freopen("D:\out.txt","w",stdout);
}
template <class T>
inline void read(T &x)
{
    char c=getchar(); x=0;
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) {x=x*10+c-'0'; c=getchar();}
}

const int maxn=100010;
int T,n,h[maxn],sz,mx,p1,p2,ll;
int path[maxn],tmp[maxn],cnt,ans[maxn];
struct Edge{int u,v,w,nx;}e[2*maxn];
int M[maxn];
bool f[maxn],g[maxn];
int P[maxn],Q[maxn],li[maxn],num;

void add(int a,int b,int c)
{
    e[sz].u=a; e[sz].v=b; e[sz].w=c;
    e[sz].nx=h[a]; h[a]=sz++;
}

void dfs(int x,int dep,int len,bool d)
{
    f[x]=1;
    if(len>mx)
    {
        if(d==0) mx=len,p1=x;
        else
        {
            mx=len,p2=x,cnt=dep;
            for(int i=0;i<cnt;i++) path[i]=tmp[i];
        }
    }
    for(int i=h[x];i!=-1;i=e[i].nx)
    {
        if(f[e[i].v]) continue;
        tmp[dep]=i;
        dfs(e[i].v,dep+1,len+e[i].w,d);
    }
}

void Find(int x,int len)
{
    g[x]=1; if(len>ll) ll=len;
    for(int i=h[x];i!=-1;i=e[i].nx)
    {
        if(f[i/2]) continue;
        if(g[e[i].v]) continue;
        Find(e[i].v,len+e[i].w);
    }
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        memset(h,-1,sizeof h); cnt=sz=0;
        for(int i=0; i<n-1; i++)
        {
            int u,v,w; scanf("%d%d%d",&u,&v,&w);
            add(u,v,w); add(v,u,w);
        }
        memset(f,mx=0,sizeof f); dfs(1,0,0,0);
        memset(f,mx=0,sizeof f); dfs(p1,0,0,1);

       // for(int i=0;i<cnt;i++) printf("%d -> %d
",e[path[i]].u,e[path[i]].v);

        memset(f,0,sizeof f);
        for(int i=0; i<cnt; i++) f[path[i]/2]=1;

        memset(g,0,sizeof g); int L=0,R;

        for(int i=0;i<cnt;i++)
        {
            ll=0; Find(e[path[i]].v,0);
            M[e[path[i]].v]=ll;
        }

        L=0; P[e[path[0]].u]=0;
        for(int i=0;i<cnt;i++)
        {
            L=L+e[path[i]].w;
            P[e[path[i]].v]=max(L+M[e[path[i]].v],P[e[path[i]].u]);
        }

        R=0; Q[e[path[cnt-1]].v]=0;
        for(int i=cnt-1;i>=0;i--)
        {
            R=R+e[path[i]].w;
            Q[e[path[i]].u]=max(R+M[e[path[i]].u],Q[e[path[i]].v]);
        }

        for(int i=0;i<cnt;i++)
        {
            int x1=P[e[path[i]].u],x2=Q[e[path[i]].v];
            ans[path[i]/2]=max(x1,x2);
        }

        for(int i=0; i<n-1; i++) if(f[i]==0) ans[i]=mx;

        LL Ans=0;
        for(int i=0;i<n-1;i++) Ans=Ans+(LL)ans[i];
        printf("%lld
",Ans);
    }
    return 0;
}