挺进

题目大意

给出一颗边权树，问你删除一条边然后将两部分直径相加的最大值为多少。

DP

我们知道求直径的dp方法：
f1[x]表示x往下走的最长链，f2[x]表示x往下走不与f1路径相交的最长链。
一颗树的直径长度=∑ni=1f1[i]+f2[i]$\sum_{i=1}^nf1[i]+f2[i]$
其中f1[i]+f2[i]表示在i的子树中，经过i的最长路径。
现在我们对于本题，一个子树内的直径，可以额外保留一个num表示子树内最长直径（不包括经过本身的路径）
那么x子树内的直径=max(f1[x]+f2[x],num[x])
我们要如何知道删除子树x剩余部分的直径？
首先，处理f3[x]表示x往下走不与f1、f2路径相交的最长链，还要处理g表示f1、f2、f3分别是往哪一个儿子里走的。
同时，要处理num[x][0/1]表示x子树中（不包含x）f1[y]+f2[y]的最大的值和次大值，同时用who[x][0/1]表示最大和次大师哪一个儿子子树中的。
设f[x]表示考虑x的父亲的子树，删除x子树后的直径。
设x父亲为y，先考虑经过y的最长路径，于是讨论一下：如果y最长链要走到x，即为f2[y]+f3[y]，如果y次长链要走到x，即为f1[y]+f3[y]，否则为f1[y]+f2[y]。
然后考虑y子树内的（不包括y），如果f1[z]+f2[z]的最大值在x子树内，即为num[y][1]否则为num[y][0]。
于是可以处理出f[x]。
接着处理g[x]表示从x出发，不能往x的子树中走，走出的最长路径长度。
那么一定要走到父亲y，一定有x到y的边权。
然后，在y可以往下走，但不能往x里走，类似上面的情况讨论一下找出y往下走不能往x里走的最长链，记为mx。也可以往上走，就是g[y]。
还要处理一个gg[x]，表示删除子树x后剩余部分的直径，显然剩余部分直径要么是f[x]，要么是mx+g[y]。
求出gg后就可以统计答案了。

#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int maxn=100000+10;
ll f1[maxn],f2[maxn],f3[maxn],num[maxn][2],who[maxn][2],f[maxn],g[maxn],gg[maxn],ans;
int g1[maxn],g2[maxn],g3[maxn],cnt[maxn];
int h[maxn],go[maxn*2],dis[maxn*2],next[maxn*2];
int i,j,k,l,t,n,m,tot;
int read(){int x=0;char ch=getchar();while (ch<'0'||ch>'9') ch=getchar();while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x;
}
void add(int x,int y,int z){go[++tot]=y;dis[tot]=z;next[tot]=h[x];h[x]=tot;
}
void dfs(int x,int y,int z){cnt[x]=z;ll mx,sum;int t=h[x];while (t){if (go[t]!=y){dfs(go[t],x,dis[t]);if (f1[go[t]]+(ll)dis[t]>=f1[x]){f3[x]=f2[x];g3[x]=g2[x];f2[x]=f1[x];g2[x]=g1[x];f1[x]=f1[go[t]]+(ll)dis[t];g1[x]=go[t];}else if (f1[go[t]]+(ll)dis[t]>=f2[x]){f3[x]=f2[x];g3[x]=g2[x];f2[x]=f1[go[t]]+(ll)dis[t];g2[x]=go[t];}else if (f1[go[t]]+(ll)dis[t]>=f3[x]){f3[x]=f1[go[t]]+(ll)dis[t];g3[x]=go[t];}mx=max(num[go[t]][0],f1[go[t]]+f2[go[t]]);if (mx>=num[x][0]){num[x][1]=num[x][0];who[x][1]=who[x][0];num[x][0]=mx;who[x][0]=go[t];}else if (mx>=num[x][1]){num[x][1]=mx;who[x][1]=go[t];}}t=next[t];}
}
void dg(int x,int y,int z){ll mx,sum;if (x!=1){if (g1[y]==x) mx=f2[y]+f3[y];else if (g2[y]==x) mx=f1[y]+f3[y];else mx=f1[y]+f2[y];if (who[y][0]==x) sum=num[y][1];else sum=num[y][0];f[x]=max(mx,sum);if (g1[y]==x) mx=f2[y];else mx=f1[y];g[x]=(ll)z+max(mx,g[y]);gg[x]=f[x];gg[x]=max(gg[x],mx+g[y]);}int t=h[x];while (t){if (go[t]!=y) dg(go[t],x,dis[t]);t=next[t];}mx=max(num[x][0],f1[x]+f2[x]);mx+=gg[x];ans=max(ans,mx);
}
int main(){freopen("data.in","r",stdin);n=read();fo(i,1,n-1){j=read();k=read();l=read();add(j,k,l);add(k,j,l);}dfs(1,0,0);dg(1,0,0);printf("%lld\n",ans);
}