题意：
给一棵树，，每条边的权值为R*I^2,求到所有其他节点权值和最小的点和相应最小权值和。
分析：
先将图转化成树，然后在树上dfs。
代码：
//poj 4045//sep9#include<iostream>#include<vector>using namespace std;const int maxN=50012;vector<int> g[maxN];int vis[maxN],bro[maxN],son[maxN];__int64 num[maxN],dis[maxN],dp[maxN];int n,I,R;void build_tree(int h){vis[h]=1;for(int i=g[h].size()-1;i>=0;–i){int x=g[h][i];if(vis[x]==0){vis[x]=1;bro[x]=son[h];son[h]=x;build_tree(x);} }}void dfs(int h,__int64& num_res,__int64& dis_res){num_res=1,dis_res=0;int s=son[h];while(s){__int64 x,y;dfs(s,x,y);num_res+=x;dis_res+=(x+y);s=bro[s];}num[h]=num_res;dis[h]=dis_res;}void ex_dfs(int h,__int64 pre_sum){dp[h]=dis[h]+pre_sum;int s=son[h];while(s){__int64 a=n-num[s];__int64 b=dis[h]-(dis[s]+num[s])+pre_sum;ex_dfs(s,a+b);s=bro[s];}} int main(){int cases;scanf("%d",&cases);while(cases–){scanf("%d%d%d",&n,&I,&R);for(int i=1;i<=n;++i) g[i].clear();for(int i=1;i<n;++i){int a,b;scanf("%d%d",&a,&b);g[a].push_back(b);g[b].push_back(a);}memset(vis,0,sizeof(vis));memset(bro,0,sizeof(bro));memset(son,0,sizeof(son));build_tree(1);memset(num,0,sizeof(num));memset(dis,0,sizeof(dis));__int64 x,y;dfs(1,x,y);ex_dfs(1,0); __int64 ans=dp[1];for(int i=1;i<=n;++i)ans=min(ans,dp[i]);printf("%I64d\n",ans*R*I*I);for(int i=1;i<=n;++i)if(dp[i]==ans)printf("%d ",i);printf("\n\n");}return 0;}
所有的赏赐都只是被用来奖励工作成果的。
