Shortest Path

题意:把图中所有节点分成对点,然后把分成的每对点的距离求和,并且要求和最小
题解: 典型的树形结构
所以我们考虑的时候,如果当前节点的子节点数为偶数那是否表示,不需要额外添加边

如图(图有点丑.....)对于下面的那个节点他有偶数个节点,两两配对即可
而对于子节 点有奇数个,那么两两配对,对于小小根还剩余1个子节点,而这个节点配对最好的方法就是和小小根配对,而对于小根的子节点数位偶数,跳过,对于根节点的节点数是奇数,那么它要和自己的某一个子节点结合
所以就是搜索全图,如果当前节点的子树节点(子树包括当前节点)为偶数不需要处理,奇数加上当前节点与其根节点的边权
时间复杂度

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1e18
ll const maxn=2e6+10;
struct node ///链式前向星存图
{
    ll to,next,val;///终点，同起点的上一条边的编号，边权
} edge[maxn]; ///边集
ll n,t,u,v,w,cnt,head[maxn],ans;
void add(ll u,ll v,ll w)
{
    edge[++cnt].next = head[u];///以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
    edge[cnt].to=v;///终点
    edge[cnt].val=w;///权值
    head[u]=cnt;///更新以u为起点上一条边的编号
}
void solve();
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
        solve();

}
ll dfs(ll a,ll b,ll c)
{
    ll tc=1;
    for(int i=head[a]; i!=0; i=edge[i].next)
    {

        ll w=edge[i].to;
        ll v=edge[i].val;
        if(w==b)
            continue;
        tc+=dfs(w,a,v);
    }
    if(tc%2==1)
        ans+=c;
    return tc;
}
void solve()
{
    memset(head,0,sizeof(head));
    scanf("%lld",&n);
    cnt=0,ans=0;
    for(int i=1; i<n; i++)
    {
        scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    dfs(1,0,0);
    printf("%lld\n",ans);
}