题意：N个点的一棵带权树。切掉某条边的价值为切后两树直径中的最大值。求各个边切掉后的价值和（共N-1项）。
解法一：
强行两遍dp，思路繁琐，维护东西较多：
dis表示以i为根的子树的直径，dis2表示切掉以i为根的子树后的直径。
第一遍dp，记录
down[][0]:从i结点向下的最大距离
down[][1]:与down[][0]无交集的向下次大距离
dis:以i为根的子树的直径
第二遍dp，记录
up:从i结点向上的最远距离, 可以是w+父节点的up，也可以是w+父节点的down（判断一下down是否与w有重合）
dis2:切掉以i为根的子树后的直径
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pii pair<int, int>
#define mp make_pair
typedef long long ll;
const int N = 1e5+;
void gmax(int& a, int b){ if(a < b) a = b;}
int n;
ll ans;
int down[N][], up[N], dis[N], dis2[N]; int head[N], nex[N*], tot;
pii edge[N*];
void init(){
tot = ;
memset(head, -, sizeof(head));
memset(down, , sizeof(down));
memset(up, , sizeof(up));
memset(dis, , sizeof(dis));
memset(dis2, , sizeof(dis2));
}
void add(int u, int v, int w){
edge[tot] = mp(v, w);
nex[tot] = head[u];
head[u] = tot++;
}
//down[][0]:从i结点向下的最大距离
//down[][1]:与down[][0]无交集的向下次大距离
//dis:以i为根的子树的直径
void dfs(int fa, int x){
// printf("dfs x %d, fa %d\n", x, fa);
//down[x][0] = down[x][1] = dis[x] = dis2[x] = up[x] = 0;
for(int i = head[x]; ~i; i = nex[i]){
int y = edge[i].X, w = edge[i].Y;
if(y == fa) continue ;
dfs(x, y);
if(down[y][]+w > down[x][])
down[x][] = down[x][], down[x][] = down[y][]+w;
else if(down[y][]+w > down[x][])
down[x][] = down[y][]+w;
gmax(dis[x], dis[y]);
}
gmax(dis[x], down[x][]+down[x][]);
}
//up:从i结点向上的最远距离
//dis2:切掉以i为根的子树后的直径
multiset<int>::iterator it;
void dfs2(int fa, int x){
if(fa != -) ans += max(dis[x], dis2[x]);
// printf("fa %d, x %d\n", fa, x);
multiset<int> se, se2;//兄弟树的直径, x往各个兄弟树的最长路
for(int i = head[x]; ~i; i = nex[i]){
int y = edge[i].X, w = edge[i].Y;
if(y == fa) continue ;
se.insert( dis[y] );
se2.insert( down[y][]+w );
}
for(int i = head[x]; ~i; i = nex[i]){
int y = edge[i].X, w = edge[i].Y;
if(y == fa) continue ;
up[y] = up[x]+w;
if(down[y][]+w == down[x][])
gmax(up[y], down[x][]+w);
else gmax(up[y], down[x][]+w);
it = se.find( dis[y] ), se.erase(it);
it = se2.find( down[y][]+w ), se2.erase(it);
dis2[y] = dis2[x];
if(!se.empty())
gmax(dis2[y], *se.rbegin());
if(se2.empty()) gmax(dis2[y], up[x]);
else gmax(dis2[y], up[x]+*se2.rbegin());
if(se2.size() >= ){
int tmp = ;
it = se2.end();
tmp += *--it;
tmp += *--it;
gmax(dis2[y], tmp);
}
dfs2(x, y);
se.insert( dis[y] );
se2.insert( down[y][]+w );
}
}
void debug(int n){
for(int i = ; i <= n; i++)
printf("%d: down0 %d, down1 %d, dis %d, dis2 %d, up %d\n", i, down[i][], down[i][], dis[i], dis2[i], up[i]);
}
int main(){
int t, u, v, w; scanf("%d", &t);
while(t--) {
init();
scanf("%d", &n);
for(int i = ; i < n; i++){
scanf("%d%d%d", &u, &v, &w);
add(u, v, w), add(v, u, w);
}
ans = ;
dfs(-, );
dfs2(-, );
printf("%lld\n", ans);
}
return ;
}
解法二：
先求出原树的直径。
从直径两端分别来一次dp
切的边不在直径上，价值为直径；
切的边在直径上，由直径两端的dp得解。