题面
WZland 的国王决定举办一个晚会，这次晚会要求所有的 WZland 居民都参 加，但是他发现 WZland 的所有城市之间的道路都已经毁坏（平时 WZland 的居 民都在自己的城市里活动，所以他们对于那些道路一点都不关心）。这是一件十 分麻烦的事情，因为这个晚会要求所有居民都来参加，于是国王决定要重建道路。 他找出了 WZland 的地图，他发现 WZland 有 N 个城市，有 M 条破败的双向 道路连接着这 N 个城市。由于周年纪念日就要到来，为了节省时间国王决定修 建的道路恰好将这 N 个城市连接起来。修建一条长度为 L 的道路，需要花费 L 个 Ws(Ws 是 WZland 的通用货币)，国王想要将总的花费降到最少，这样他能有 足够多的钱来举办晚会。国王还有一个要求，因为这些道路是同时开始修建的， 因此修建完这些道路的总时间等于修建完最长的那条道路的时间（你可以认为所 有工人的修建速度是一样的，即一单位时间修建 1 单位长度的道路），国王想要 总的修建时间最少。 由于要举行晚会，国王需要找到一个地点来举办晚会，这同样是一件十分麻 烦的事情。因为 WZland 的每个人都十分懒，他们不愿意多走路（就连在这周年 纪念日也不例外）。 WZland 的居民每走 1 单位长度的路就会产生 1 单位的不高 兴度（这就是为什么他们都不愿离开自己城市的原因）。WZland 的国王想要这个 晚会的不高兴度尽量低（晚会的不高兴度就等于所有参加晚会的人的不高兴度的 和），这就要求选取一个合适的地点来举办晚会（WZland 的居民要通过即将修建 好的道路，来到这个晚会举办地）。 举个例子，如果晚会在城市 u 举行，城市 i 有 Pi 个人，城市 u 和城市 i 的距 离为 D(u,i)，那么这些人产生的不高兴度之和为 Pi*D(u,i)。 国王把这个任务交给了你，他希望你能找出一个地点，是所有人的不高兴度 之和最小。
分析
显然第一个子问题是最小生成树
关键在于第二个问题如何处理
第一次看到的时候会想到树的中心之类的，但是它多了一个每个点的点权的限制，就很困难了。
因为最后已经是一棵树了，所以会想到树形dp
如果是从儿子转移到父亲，那就要以每个点为根dfs，才将子节点到根的不高兴度全部处理出来，并且才能比较出最小的，很显然这是30分做法
所以考虑从父亲转移到儿子，假设已经处理了以当前节点v的父亲节点u为根的不高兴度dp[u]，显然，当前节点到父亲节点，以及以当前节点为根的子树中的所有节点的不高兴度都会少(p为点权)p[ ]*dis[u,v]。因为这些节点全部都不用去u节点了，只需要去v节点了，所以不用再通过这条路。但是相应的，本来除了v的子树的其他节点都是不用通过e(u,v)的，现在为了到v，必须从u通过这条路，则除了以v为子树的节点，每个节点都要产生p[ ]*dis[u,v]的不高兴度。
所以 dp[v]=dp[u]-siz[v]*dis[u,v]+(total-siz[v])*dis[u,v]。
化简一下 dp[v]=dp[u]+(total-2*siz[v])*dis[u,v]。
因为是一棵生成树，就随便以一个点为根，预处理一下子树大小，预处理一下那个点的不高兴度，再从那个点开始深搜实现dp
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cmath> using namespace std; #define N 100100 #define ll long long #define INF 0x7fffffff7fffffff ll first[N],p[N],fa[N],siz[N],dp[N],pre[N],dis[N]; ll n,m,t,cnt,cot,num,len,tot,ans,ansnum; struct email { ll u,v,w; ll nxt; }e[N*10],g[N*5]; inline void rebuild(ll u,ll v,ll w) { e[++cnt].nxt=first[u];first[u]=cnt; e[cnt].v=v;e[cnt].u=u;e[cnt].w=w; } inline void add(ll u,ll v,ll w) { g[++cot].v=v;g[cot].u=u;g[cot].w=w; } inline ll find(ll x) { return fa[x]==x?x:fa[x]=find(fa[x]); } bool cmp(email a,email b) { return a.w<b.w; } inline void read(ll &x) { x=0;ll f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} x=x*f; } void kruskal() { for(ll i=1;i<=n;i++)fa[i]=i; sort(g+1,g+1+m,cmp); for(ll i=1;i<=m;i++) { ll u=g[i].u,v=g[i].v,w=g[i].w; ll fax=find(u),fay=find(v); if(fax!=fay) { fa[fax]=fay; rebuild(u,v,w);rebuild(v,u,w); len+=w;num++; } if(num==n-1){t=w;break;} } } void dfs(ll u,ll f) { for(ll i=first[u];i;i=e[i].nxt) { ll v=e[i].v,w=e[i].w; if(v==f)continue; dfs(v,u); siz[u]+=siz[v]; dis[v]=w; pre[u]+=pre[v]+siz[v]*dis[v]; } } void DP(ll u,ll f) { if(u!=1) dp[u]=dp[f]+dis[u]*(tot-2*siz[u]); for(ll i=first[u];i;i=e[i].nxt) { ll v=e[i].v,w=e[i].w; if(v==f)continue; DP(v,u); } } int main() { freopen("anniversary.in","r",stdin); freopen("anniversary.out","w",stdout); read(n);read(m); for(ll i=1;i<=n;i++) read(p[i]),tot+=p[i],siz[i]=p[i]; for(ll i=1;i<=m;i++) { ll u,v,w; read(u);read(v);read(w); add(u,v,w); } kruskal(); printf("%lld %lld ",len,t); dfs(1,-1); dp[1]=pre[1];DP(1,-1); ans=INF; for(ll i=1;i<=n;i++) if(dp[i]<ans) ans=dp[i],ansnum=i; printf("%lld %lld ",ansnum,ans); return 0; }