【題目連結】 http://www.lydsy.com/JudgeOnline/problem.php?id=1827
【題目大意】
給出一棵有點權和邊權的樹,
請确定一個點,使得每個點到這個點的距離乘上該點乘積的總和最小。
【題解】
定1為根,我們先計算當這個點為1的時候的值,同時記錄每個子樹的size
之後我們再做一遍dfs,計算出每個點作為中心時候的答案
我們發現當一個點從父節點往子節點移動的時候
對于答案的變化是ans+=(size[1]-2*size[x])*len(fx->x)
是以我們dfs計算,保留最小值即可。
【代碼】
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
const int N=100010;
typedef pair<int,int> P;
typedef long long LL;
vector<P> v[N];
int d[N],size[N],n;
LL ans,ans1;
void dfs(int x,int fx){
for(int i=0;i<v[x].size();i++){
int y=v[x][i].first,z=v[x][i].second;
if(y!=fx){
d[y]=d[x]+z;
ans+=(LL)size[y]*d[y];
dfs(y,x);
size[x]+=size[y];
}
}
}
void dfs2(int x,int fx){
for(int i=0;i<v[x].size();i++){
int y=v[x][i].first,z=v[x][i].second;
if(y!=fx){
ans1+=(LL)(size[1]-2*size[y])*z;
if(ans1<ans)ans=ans1;
dfs2(y,x);
ans1-=(LL)(size[1]-2*size[y])*z;
}
}
}
int main(){
while(~scanf("%d",&n)){
ans=ans1=0;
for(int i=1;i<=n;i++)scanf("%d",&size[i]);
for(int i=1;i<n;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
v[a].push_back(P(b,c));
v[b].push_back(P(a,c));
}dfs(1,-1);ans1=ans;
dfs2(1,-1);
printf("%lld\n",ans);
}return 0;
}
轉載于:https://www.cnblogs.com/forever97/p/bzoj1827.html