Great Cow Gathering G|P2986

https://www.luogu.com.cn/problem/P2986

题目描述

Bessie 正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。

每个奶牛居住在 N 个农场中的一个，这些农场由 N-1 条道路连接，并且从任意一个农场都能够到达另外一个农场。道路 i连接农场 Ai​ 和 Bi，长度为 Li​。集会可以在 N 个农场中的任意一个举行。另外，每个牛棚中居住着 Ci​ 只奶牛。

在选择集会的地点的时候，Bessie 希望最大化方便的程度（也就是最小化不方便程度）。比如选择第 X 个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和（比如，农场 i 到达农场 X 的距离是 20，那么总路程就是 Ci×20）。帮助 Bessie 找出最方便的地点来举行大集会。

输入格式

第一行一个整数 N 。

第二到 N+1 行：第 i+1 行有一个整数 Ci。

第 N+2 行到 2N 行：第 i+N+1 行为 3 个整数：Ai,Bi​ 和 Li​。

输出格式

一行一个整数，表示最小的不方便值。

输入输出样例

输入 #1

5 
1 
1 
0 
0 
2 
1 3 1 
2 3 2 
3 4 3 
4 5 3

输出 #1

15

说明/提示

1≤N≤100000，1≤Ai≤Bi≤N，0≤Ci,Li≤1000。

板子题，但我不会

确信

题意很简单，在有边权有点权的一棵无根树上选一点为根，使得所有节点到根的路径长乘点权之和最小。

首先，既然是无根树，这个树就不能太规整，要长得洒脱一些，便于我们观测：

首先，最朴素的方法，每个点都作为根算一遍

O(n^2)=O(TLE)

所以

不可以哦～

那咋做呢

我们看看哪里有严重浪费。

比如，我们在算相邻的节点时，会发现，除了这两点的子树和sz有变化，其他的sz都没有变化，而我们做那么多遍dp显然浪费了。

嗯——

那我们就可以先随便找一个点当作根，先算出一种情况，O(n)很快的

然后从这个基根向四周dfs,由于dfs回溯的特性，每次只用改一小部分，也就是两个sz

新的dp也能很简单的算出来：假设从u换根到v，u到v的这条边权为w，那v的子树的贡献就减小了sz[v]*w，而换到v后，u作为v的子树，对答案的贡献增加了sz[u]*w， dp就转移成功了。

但显然发现，第二个sz不能直接用，因为这时的sz[u]还是u为根时的子树和.

那——怎么办呢？

稍加计算，我们发现，根处的sz永远是整棵树的和，不变，那把sz[u]赋给sz[v]即可;

嗯？

u作为v的子树，它的大小应当是整棵树的大小减去u还是根时v子树的大小，剩下的便是u作为新子树时的sz

记得回溯回来就好啦

显然，换完所有根都试一遍复杂度也只有O(n)，过了。

#include<iostream>
#include<cstring>
#define int long long 
using namespace std;
int n;
const int MAXN=1e5+10;
//快读读，读快快～
inline int read(){
    int s=0,f=1;
    char c=getchar();
    while(c<48 || c>57){if(c=='-')f=-f;c=getchar();}
    while(c>=48 && c<=57)s=s*10+c-48,c=getchar();
    return s*f;
}
int w[MAXN];//点权
struct tree{
    int to;
    int w;
    int next;
}edge[MAXN*2];
int head[MAXN];
int _cnt;
void add(int u,int v,int w){
    edge[++_cnt].to=v;
    edge[_cnt].w=w;
    edge[_cnt].next=head[u];
    head[u]=_cnt;
}
//把1dfs掉！
int sz[MAXN];
int dp[MAXN];
bool vis[MAXN];
int dfs(int x,int dep){
    vis[x]=1;
    sz[x]=w[x];
    int ret=dep*w[x];
    //生娃娃  
    for(int i=head[x];i!=0;i=edge[i].next){
        int nxt=edge[i].to;
        if(vis[nxt])continue;
        ret+=dfs(nxt,dep+edge[i].w);
        sz[x]+=sz[nxt];
    }
    return ret;    
}
//换根咯~
int minn=0x7fffffffffffffff;
void chg_root(int r){
    vis[r]=1;
    minn=min(minn,dp[r]);
    //sons
    for(int i=head[r];i!=0;i=edge[i].next){
        int nxt=edge[i].to;
        if(vis[nxt])continue;
        dp[nxt]=dp[r];
        dp[nxt]-=edge[i].w*sz[nxt];
        int diff=sz[r]-sz[nxt];
        sz[nxt]=sz[r];
        sz[r]=diff;        
        dp[nxt]+=edge[i].w*sz[r];
        chg_root(nxt);
        sz[r]=sz[nxt];
        sz[nxt]-=diff;
    }
    return;
}
signed main(){
    n=read();    
    int u,v,k;
    for(int i=1;i<=n;i++)w[i]=read();
    for(int i=1;i<n;i++){
        u=read(),v=read(),k=read();
        add(u,v,k);
        add(v,u,k);
    }
    //先是1
    int pre=dfs(1,0);
    memset(vis,0,sizeof(vis));
    dp[1]=pre;
    chg_root(1);
    cout<<minn;
    //要相信光！！！！！
    //相信个鬼哟。。
    //相信汝社
        
    return 0;
}