分析

　　　很明显这是道树形dp。

　　如果没有传送门的话，树上的距离之和就是边权之和的2倍，但是可以用传送省掉某些边，所以开数组dp[i][1/0]表示在i号结点放/不放传送门能省掉的最大权值。

　　通过分析可得，对于以任意一个结点为根的子树，如果把传送门放在这个结点上的话，那么与ta相连的每个点都可以直接传送会来，所以dp[u][1]+=max(dp[v][0]+edge[i].val,dp[v][1])。

　　如果不放的话，就只能把与这个结点的相连的最长子链给省掉，并且那条子链也不能放传送门（不然回不去了），

所以dp[u][0]=max(dp[u][0],dp[v][0]+edge[i].val)。

 

code 

#include
     
      #define maxn 1000010#define ll long longusing namespace std;int n,head[maxn],k;ll sum,dp[maxn][2];struct node{    int to,nxt;    ll val;} edge[maxn*2];void add(int u,int v,ll w){    edge[++k].nxt=head[u];    edge[k].to=v;    edge[k].val=w;    head[u]=k;}void dfs(int u,int fa){    for(int i=head[u];i;i=edge[i].nxt)    {        int v=edge[i].to;        if(v==fa) continue ;        dfs(v,u);        dp[u][1]+=max(dp[v][0]+edge[i].val,dp[v][1]);        dp[u][0]=max(dp[u][0],dp[v][0]+edge[i].val);    }}int main(){
        scanf("%d",&n);    int x,y;    ll z;    for(int i=1;i