[数据结构与算法]换根dp 洛谷+upc

题目描述

有一个村庄居住着 nn 个村民，有 n-1n?1 条路径使得这 nn 个村民的家联通，每条路径的长度都为 11。现在村长希望在某个村民家中召开一场会议，村长希望所有村民到会议地点的距离之和最小，那么村长应该要把会议地点设置在哪个村民的家中，并且这个距离总和最小是多少？若有多个节点都满足条件，则选择节点编号最小的那个点。

输入格式

第一行，一个数 nn，表示有 nn 个村民。

接下来 n-1n?1 行，每行两个数字 aa 和 bb，表示村民 aa 的家和村民 bb 的家之间存在一条路径。

输出格式

一行输出两个数字 xx 和 yy。

xx 表示村长将会在哪个村民家中举办会议。

yy 表示距离之和的最小值。

输入输出样例

输入 #1复制

4
1 2 
2 3 
3 4 

输出 #1复制

2 4

说明/提示

数据范围

对于 70\%70% 数据 n \le 10^3n≤103。

对于 100\%100% 数据 n \le 5 \times 10^4n≤5×104。

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int d[N];//为根为1时服务
int f[N];//dp时的核心
int n,cnt;
int size[N];//子树中包括自己节点的个数
bool vis[N];
int head[N];
struct Edge
{
    int to,nxt;
} edge[N<<1];
void add(int x,int y)
{
    edge[++cnt].to=y;
    edge[cnt].nxt=head[x];
    head[x]=cnt;
}
void dfs1(int now,int fa)
{
    size[now]=1;
    for(int i=head[now]; i; i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(to==fa) continue;//已经算过的点不要
        d[to]=d[now]+1;
        dfs1(to,now);
        size[now]+=size[to];
    }
}
void dfs(int now,int fa)
{
    f[now]=f[fa]+n-2*size[now];//树形dp核心部分
    for(int i=head[now]; i; i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dfs(to,now);
    }
}
signed main()
{
    scanf("%d",&n);
    for(int x,y,i=1; i<n; i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    d[1]=1;
    dfs1(1,-1);
    int maxn=0,idx=1;
    for(int i=1; i<=n; i++) maxn+=d[i];
    maxn-=n;
    f[1]=maxn;
    for(int i=head[1]; i; i=edge[i].nxt)
    {
        int to=edge[i].to;
        dfs(to,1);
    }
    for(int i=2; i<=n; i++)
    {
        if(f[i]<maxn) maxn=f[i],idx=i;
    }
    printf("%d %d",idx,maxn);
    return 0;
}

BLUESKY007喜欢种树。一天，她得到了一棵nn个点的树，其中节点ii重量为wiwi?。在种树之前，BLUESKY007需要用起重机把树吊起。由于她只有一台起重机，所以她只能选择一个点作为受力点。根据BLUESKY007所在世界的物理知识，吊起一棵树需要做的功为∑ni=1wi?disi∑i=1nwi?disi，其中disidisi表示节点ii与受力点之间的距离（边数）。

由于吊起这棵树的费用与所做的功正相关，所以BLUESKY007希望所做的功尽可能小。请你帮助她求出吊起这棵树所做的功的最小值。

题解

本题是裸的换根DP，很好实现。设以1为根结点，dep[u]表示u到根的路径长度，size[u]表示以u为根的子树中所有结点的重量和，当以1为根结点时，dfs一遍求出总做功的值，即sum=∑w[u]?dep[u]sum=∑w[u]?dep[u]。接着考虑换根带来的影响，当根从u换到儿子结点v时，v所在的子树少做功size[v]，v外的结点多做功size[1]-size[v]，即sum′=sum?size[v]+(size[1]?size[v])=sum?2?size[v]+size[1]sum′=sum?size[v]+(size[1]?size[v])=sum?2?size[v]+size[1]。
要使sum′≤sumsum′≤sum，则sum?2?size[v]+size[1]≤sumsum?2?size[v]+size[1]≤sum，即size[1]≤2?size[v]size[1]≤2?size[v]，所以在换根时，只有满足2?size[v]≥size[1]2?size[v]≥size[1]的儿子结点v才可能使得总做功值变小，可以利用这个条件进行剪枝。

#include<bits/stdc++.h>
using namespace std;
const int N=2*1e5+5;
int n,w[N];
long long size[N],dep[N],sum,ans=1e18;
vector<int> g[N];
void dfs(int u,int fa){
	sum+=w[u]*dep[u];
	size[u]=w[u];
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa)continue;
		dep[v]=dep[u]+1;
		dfs(v,u);
		size[u]+=size[v];
	}
}
void change_root(int u,int fa,long long sum){
	ans=min(ans,sum);
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa)continue;
		long long tmp=sum-2*size[v]+size[1];
		if(2*size[v]>=size[1])change_root(v,u,tmp);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&w[i]);
	}
	for(int i=1,u,v;i<n;i++){
		scanf("%d %d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,-1);
	change_root(1,-1,sum);
	printf("%lld",ans);
}