Shortest Path题解

这个题还是好心的群友教我的...加群的好处..我不会一点图论知识,子树都不会求.群友给我讲的.其实思路我还是懂=-=就是不会写.
下面先给大家看看两幅图:

算下两幅图的满足题意边权,第一幅图边权是1+2+3,第二幅图的边权是1+3.
我们很容易发现假如子树个数为奇数这条边就需要+,假如为偶数这条边就不用加.
按着思路写下代码就好了.

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
#define inf 132913423039
typedef long long ll;
const ll mod=1e9+7;
const ll N=1e4+5;
const ll M=10+5;
const double eps=1e-7;
using namespace std;
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b) { return a*b/gcd(a,b);    }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a = (a*a)%p;b >>= 1;}return ans%p;}
ll Inv(ll x)          { return qp(x,mod-2,mod);}
ll C(ll n,ll m){if (m>n) return 0;ll ans = 1;for (int i = 1; i <= m; ++i) ans=ans*Inv(i)%mod*(n-i+1)%mod;return ans%mod;}
ll A(ll n,ll m,ll mod){ll sum=1; for(int i=n;i>=n-m+1;i--) sum=(sum*i)%mod; return sum%mod;}
ll lowbit(ll x) {return x&(-x);}
ll c[N],sum1[N],sum2[N],a[N],lsh[N],n,m,s;
void add1(ll i,ll k){ while(i<=n) {c[i]+=k;i+=lowbit(i);}}//预处理ai单点修改 区间查询***预处理a[i]-a[i-1]区间修改单点查询
ll  Sum1(ll i) {ll res=0; while(i>0) res+=c[i],i-=lowbit(i);return res;}//预处理ai单点修改 区间查询***预处理a[i]-a[i-1]区间修改单点查询
void add2(ll i,ll k){ ll x=i;while(i<=n) {sum1[i]+=k;sum2[i]+=k*(x-1);i+=lowbit(i);}}//区间修改,区间查询
ll  Sum2(ll i) {ll res=0,x=i;while(i>0){ res+= x * sum1[i]-sum2[i]; i -= lowbit(i);}return res;}//区间修改,区间查询
void ls(){ll cnt; for(ll i=1;i<=n;i++) lsh[i]=a[i]; sort(lsh+1,lsh+n+1);cnt = unique(lsh+1,lsh+n+1)-lsh-1; for(int i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh;}
ll dp[N];
ll ans=0;
struct dd
{
  ll son,val;//存边权和子节点
};
vector<dd>v[N];
ll cnt[N];
ll dfs(ll x,ll fa)//统计节点,记录权值
{
    if(v[x].size()==1&&x!=1) return cnt[x]=1;//假如没有子节点,子树大小就是1
    cnt[x]=1;
    for(ll i=0;i<v[x].size();i++)
    {
        ll so=v[x][i].son;
        ll va=v[x][i].val;
        if(so==fa) continue;
        cnt[x]+=dfs(so,x);//子树大小等于当前这个点+所有儿子的子树大小
        if(cnt[so]%2==1) ans+=va;     //假如那个点子树大小是奇数,那么就+
    }
    return cnt[x];
}

signed main()
{
    ios;
    ll x,y,z,t;
    cin>>t;
    while(t--)
    {
       ans=0;
       cin>>n;//n个点m条边,s为根
       for(ll i=1;i<=n;i++) v[i].clear(),cnt[i]=0;
       for(ll i=1;i<=n-1;i++)
       {
         cin>>x>>y>>z;
         v[x].pb(dd{y,z});
         v[y].pb(dd{x,z});
       }
       dfs(1,0);
       cout<<ans<<endl;
    }
    return 0;
}

=-=感觉挺简单的