題目大意:
有一棵樹,每條邊有權值,從樹上一點到另一點的路徑權值為該條路徑上的最小權邊,選一個點使得該點到其余所有點的路徑權值和最大.
題目思路:
看一下規模,可能是貪心,dp,線段樹之類的,線段樹明顯沒想法,dp嘛,狀態太多了,那就想想貪心,不過不管是什麼方法,最終的目的就是要得到一個有根樹,這裡我們可以用並查集+路徑壓縮來做.
貪心我們只要考慮構樹是按邊的權值降序還是升序,如果選用升序的話,當前邊要到前面加入的邊的限制,所以就麻煩了,而降序呢,前面加入的邊是受當前邊的限制,所以相對容易多了.
對與每個父親還要保存到其子孫的路徑權值和以及子孫數量,這在合並兩棵樹是要用到.
1)兩個點均無父親,任選一個作為父親.
2)其中一個無父親,把有父親的父親作為無父親的父親(很繞口= =...將就一下).
3)均有父親,那麼就要判斷一下到底誰做父親可以使構成的樹路徑權值更大,在這邊就要用到路徑權值和以及子孫數量了(我是用到了,大牛可能不需要...).
代碼:
[cpp]
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define ls rt<<1
#define rs ls|1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define middle (l+r)>>1
#define eps (1e-9)
#define type int
#define clr_all(x,c) memset(x,c,sizeof(x))
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1))
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
#define M 200000 +5
template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;}
template <class T> T _max(T x,T y){return x>y? x:y;}
template <class T> T _min(T x,T y){return x<y? x:y;}
int test,cas;
int n,m;
struct node{
int u,v;
ll c;
void read(){
scanf("%d%d%lld",&u,&v,&c);
}
bool operator < (const node &t) const{
return c > t.c;
}
}p[M];
ll sum[M],cnt[M];
int fa[M];
int Find(int x){
for(;x!=-1 && x!=fa[x];x=fa[x]);
return x;
}
void Union(int u,int v,ll val){
int uf=Find(u),vf=Find(v);
if(uf==-1 && vf==-1)
fa[u]=v,sum[v]+=val,cnt[v]++,fa[v]=v;
else if(uf==-1)
fa[u]=vf,sum[vf]+=val,cnt[vf]++;
else if(vf==-1)
fa[v]=uf,sum[uf]+=val,cnt[uf]++;
else{
ll tu=sum[uf]+(cnt[vf]+1)*val;
ll tv=sum[vf]+(cnt[uf]+1)*val;
if(tu > tv) fa[vf]=uf,sum[uf]=tu,cnt[uf]+=cnt[vf]+1;
else fa[uf]=vf,sum[vf]=tv,cnt[vf]+=cnt[uf]+1;
}
}
void run(){
int i,j;
clr(sum,0,n),clr(cnt,0,n);
clr(fa,-1,n);
m=n-1;
for(i=0;i<m;i++)
p[i].read();
sort(p,p+m);
for(i=0;i<m;i++)
Union(p[i].u,p[i].v,p[i].c);
for(i=1;i<=n;i++) if(cnt[i]+1==n){
printf("%lld\n",sum[i]);
return;
}
}
void preSof(){
}
int main(){
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
preSof();
//run();
while(~scanf("%d",&n)) run();
//for(scanf("%d",&test),cas=1;cas<=test;cas++) run();
return 0;
}
