题面
CJY很喜欢吃奶酪，于是YJC弄到了一些奶酪，现在YJC决定和CJY分享奶酪。
YJC弄到了n-1块奶酪，于是他把奶酪挂在了一棵n个结点的树上，每根树枝上挂一块奶酪，每块奶酪都有重量。
YJC和CJY决定这样分奶酪：首先砍掉一根树枝，把树分成两部分，每人取一部分，然后各自在自己取的那部分树上选择一条路径并取走路径上的奶酪，然后把剩下的奶酪拿去喂老鼠。
两人都想让自己取走总重量尽量大的奶酪，但他们不知道砍掉哪一根树枝最好。所以他们想让你计算，对于每一根树枝，砍掉之后每个人取走的奶酪的总重量的最大值。
对于100%的数据，保证n<=4*10^6,w<=10^6
100
可以利用树形dp直接做。
维护：
1.一个点往下的最长链(f_i)；
2.一个点往下的次长链(g_i)；
3.一个点往下的次次长链(h_i)；
4.一个子树内的最长链(mx_i)；
5.一个点的所有儿子(mx)的最大值(mxx_i)；
6.一个点的所有儿子(mx)的次大值(mxxx_i)；
7.一个点往上走的最长链(F_i)；
8.不包含一个点及其子树的最长链(Mx_i)
最后答案就是(mx)和(Mx)。
时间复杂度为(O(n))。
为什么可以用树形dp
树静态。
Code
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
#define fo(i,x,y) for(ll i=x;i<=y;i++)
#define fd(i,x,y) for(ll i=x;i>=y;i--)
using namespace std;
const char* fin="cheese.in";
const char* fout="cheese.out";
const ll inf=0x7fffffff;
const ll maxn=4000007,maxm=maxn*2;
const ll mo=2333333333333333;
ll n,bz[maxn],id,fi[maxn],la[maxm],ne[maxm],va[maxm],tot=1,tmb,ban;
ll f[maxn],g[maxn],h[maxn],mx[maxn],mxx[maxn],mxxx[maxn],fa[maxn],F[maxn],Mx[maxn];
ll ans,ans1,ans2;
void add_line(ll a,ll b,ll c){
tot++;
ne[tot]=fi[a];
la[tot]=b;
va[tot]=c;
fi[a]=tot;
}
void dfs(ll v,ll from){
for(ll k=fi[v];k;k=ne[k])
if (la[k]!=from){
fa[la[k]]=v;
dfs(la[k],v);
mx[v]=max(mx[la[k]],mx[v]);
ll tmp=f[la[k]]+va[k];
if (tmp>=f[v]){
h[v]=g[v];
g[v]=f[v];
f[v]=tmp;
}else if (tmp>=g[v]){
h[v]=g[v];
g[v]=tmp;
}else if (tmp>=h[v]) h[v]=tmp;
if (mx[la[k]]>=mxx[v]){
mxxx[v]=mxx[v];
mxx[v]=mx[la[k]];
}else if (mx[la[k]]>=mxxx[v]) mxxx[v]=mx[la[k]];
}
mx[v]=max(mx[v],f[v]+g[v]);
}
void Dfs(ll v,ll from){
for(ll k=fi[v];k;k=ne[k])
if (la[k]!=from){
Mx[la[k]]=Mx[v];
if (mx[la[k]]==mxx[v]) Mx[la[k]]=max(Mx[la[k]],mxxx[v]);
else Mx[la[k]]=max(Mx[la[k]],mxx[v]);
if (f[v]==f[la[k]]+va[k]){
F[la[k]]=max(F[v]+va[k],g[v]+va[k]);
Mx[la[k]]=max(Mx[la[k]],g[v]+max(h[v],F[v]));
}else{
F[la[k]]=max(F[v]+va[k],f[v]+va[k]);
if (g[v]==f[la[k]]+va[k]) Mx[la[k]]=max(Mx[la[k]],f[v]+max(h[v],F[v]));
else Mx[la[k]]=max(Mx[la[k]],f[v]+max(g[v],F[v]));
}
Dfs(la[k],v);
}
}
ll read(){
ll 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;
}
int main(){
freopen(fin,"r",stdin);
freopen(fout,"w",stdout);
n=read();
fo(i,1,n-1){
ll j=read();
ll k=read();
ll l=read();
add_line(j,k,l);
add_line(k,j,l);
}
dfs(1,0);
Dfs(1,0);
fo(i,1,n-1){
ll u=la[i*2+1],v=la[i*2];
if (fa[v]==u) swap(u,v);
ans1=mx[u];
ans2=Mx[u];
ans=(ans+max(ans1,ans2)*23333+min(ans2,ans1)*2333+233*i*i+23*i+2)%mo;
//printf("%lld %lld
",ans1,ans2);
}
cout<<ans<<endl;
return 0;
}