【CCF 201909-5】城市规划(LCA+暴力全排列40 & 树形dp100) Apare_xzc

城市规划(ccf 201909-5)

---

题面：

思路

1. 我一看求树上的距离，就想到了很喜欢的LCA, 可以O(1)求距离，然后又看m个节点选K个，一看，我能不能暴力dfs出C(m,k)的全排列呢？计算一下复杂度，发现前4个测试点可以过掉，于是先开心地写一发巨长的暴力（大的数据sort瞎搞的，没骗到分）

LCA + dfs暴力枚举点

//用户名   试题名称	提交时间	    代码长度	  编程语言	评测结果	得分	时间使用	空间使用
//<许智超> 城市规划	11-22 10:59	3.180KB	  C0X	    错误	40	    3.078s	15.37MB
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+100;
const int maxm = 2e5+100;
int head[maxn],tot;
struct Node{
	int to,Next,d;
}node[maxm];
void initEdge()
{
	tot = 0; 
	memset(head,-1,sizeof(head));
}
void addedge(int from,int to,int d)
{
	node[tot].to = to;
	node[tot].d = d;
	node[tot].Next = head[from];
	head[from] = tot++;
}
int good[100500];
int First[maxn],cnt;
int dfn[maxn*2];
int deep[maxn*2];
int father[maxn];
int disToRoot[maxn];
int idd[maxn]; ///是干啥用的？ 
bool vis[maxn];
bool cmp(int x,int y)
{
	return disToRoot[x]<disToRoot[y];
}
void dfs(int x,int dep)
{
	vis[x] = true;
	dfn[++cnt] = x;
	deep[cnt] = dep;
	First[x] = cnt;
	for(int i=head[x];i!=-1;i=node[i].Next)
	{
		int to = node[i].to;
		int d = node[i].d;
		if(vis[to]) continue;
		father[to] = x;
		disToRoot[to] = disToRoot[x]+d; 
		dfs(to,dep+1);
		dfn[++cnt] = x;
		deep[cnt] = dep;	
	}	
}
int ST[maxn][20];
int Log2[maxn]={-1};
void preRMQ(int m)
{
	int n = m*2-1;       
	for(int j=1;j<=n;++j) ST[j][0] = j;
	for(int i=1;(1<<i)<=n;++i)
	{
		for(int j=1;j+(1<<i)-1<=n;++j)
		{
			int a = ST[j][i-1], b = ST[j+(1<<(i-1))][i-1];
			ST[j][i] = deep[a]>deep[b]?b:a;
		}
	}
} 
int LCA(int xx,int yy)
{
	int x = First[xx], y = First[yy];
	if(x>y) swap(x,y);
	int i = Log2[y-x+1];
	int a = ST[x][i], b = ST[y-(1<<i)+1][i];
	int p = deep[a]>deep[b]?b:a;
	return dfn[p];
}
long long calDis(int px,int py)
{
	int fa = LCA(px,py);
	return disToRoot[px]-disToRoot[fa]-disToRoot[fa]+disToRoot[py];
}
int r[105000];
bool hasCelected[201900];
long long ans;
void solve(int k,int flag=0) //计算K个点两两之间的最短距离 
{
	long long sum = 0; 
	for(int i=1;i<=k;++i)
	{
		for(int j=i+1;j<=k;++j)
			sum += flag?calDis(r[i],r[j]):calDis(good[r[i]],good[r[j]]);
	}
	if(ans>sum) ans = sum;
}
void f1(int x,int M,int k) //C(M,k)
{
	if(x==k+1)
	{
		solve(k);
		return;
	}
	for(int i=r[x-1]+1;i<=M;++i)
	{
		if(hasCelected[i]) continue;
		hasCelected[i] = true;
		r[x] = i;
		f1(x+1,M,k);
		hasCelected[i] = false;
	}
}
int main()
{
	int n,m,k,NN,x,y,d;
	scanf("%d%d%d",&n,&m,&k);
	NN = n*2+10;
	for(int i=1;i<NN;++i)
		Log2[i] = Log2[i>>1]+1;
	for(int i=1;i<=m;++i)
		scanf("%d",good+i);
	initEdge();
	for(int i=1;i<n;++i)
	{
		scanf("%d%d%d",&x,&y,&d);
		addedge(x,y,d);
		addedge(y,x,d); 
	}
	cnt = 0;
	int root = good[1];
	father[root] = root;
	disToRoot[root] = 0; //root = 1 
	dfs(root,1);
	preRMQ(n);
	if((m<=2000&&k<=2)||(m<=16&&k<=16))  
	{
		ans = 1e16;
		r[0] = 0;
		f1(1,m,k);
		printf("%lld\n",ans);
	}
	else 
	{
		ans = 1e16;
		int upM = m;
		if(m>2000) upM = 2000;
		for(int kk=1;kk<=upM;++kk)
		{
			cnt = 0;
			for(int i=0;i<=n;++i) vis[i] = false;
			int root = kk;
			father[root] = root;
			disToRoot[root] = 0; //root = 1 
			dfs(root,1);
			preRMQ(n);	
			for(int i=1;i<=m;++i) idd[i] = good[i];
			sort(idd+1,idd+1+m,cmp);
			for(int i=1;i<=k;++i) r[i] = idd[i];
			solve(k,1);
		}
		printf("%lld\n",ans);
	}
	return 0;	
} 

思路：

2. 想不到什么好办法，于是去网上看题解，只有一个大牛写了题解，链接：https://blog.csdn.net/code92007/article/details/102022390

是树形DP，我觉得非常妙。而且这种2e3左右的很多都是N^2的DP

我们换个思路，不直接枚举点，而是计算每条边对于答案的贡献

———————————————————————————————————

dp[u][p] 表示的是以u为根节点的这棵树中,选取了p个点的距离之和的最小值
    要满足恰好选了K个点，那么如果以u为根节点的数中选了p个点，那么整个树
除了u这棵子树的所有树all-u就要选q个子节点
对于u的儿子节点v     u,v,w

令 tmp[p] = dp[u][p] 
先往下搜索子节点v，得到dp[v][...]的信息
父节点u和子节点v之间的边长为w
然后我们来更新dp[u][...]
最终的答案是dp[root][K]      

对于u->v:w 这条边来说
在还没有用v来更新u之前，子树v对于树u的贡献为0，
就是说现在的以u为根的树tree(u)相当于tree(u)去掉了以v为根节点的子树，即为tree(u-v)
如果要从子树tree(v)中选p个重要节点，那么tree(root-v)中就要选K-p个
那么状态是怎么转移的呢？
如果在tree(v)中选了x个点，在tree(root-v)中选了y个点，那么计算总距离的时候u->v:w这条
边对答案的贡献是 w * (x*y) 

/*
用户名	 	试题名称	提交时间	 代码长度  编程语言  评测结果	得分	时间使用  空间使用
<许智超> 	城市规划	11-23 10:41	 2.626KB   C0X	正确	100	    140ms	  21.63MB
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4+100;
int head[maxn],tot;
struct Node{
	int to,Next,d;
}node[maxn*2];
void initEdge()
{
	tot = 0;
	memset(head,-1,sizeof(head));
}
void addedge(int from,int to,int d)
{
	node[tot].to = to;
	node[tot].d = d;
	node[tot].Next = head[from];
	head[from] = tot++;
}
int dp[maxn][102],k;
int tree_u_v[102];
bool good[maxn];
int  num[maxn]; //num[u]表示以u为根节点的树中重要节点的个数 
//get到一种新的写法，对于树的遍历不用vis,只要遍历子节点的时候，if(v==fa) continue就好了 
void dfs(int u,int fa)
{
	dp[u][0] = 0; //初始化 
	if(good[u])
	{
		dp[u][1] = 0; 
		num[u] = 1; 
	} 
	for(int i=head[u];i!=-1;i=node[i].Next)
	{
		if(node[i].to==fa) continue;
		int v = node[i].to;
		int d = node[i].d;
		dfs(v,u);
		for(int j=0;j<=k;++j)
			tree_u_v[j] = dp[u][j];
		int nU = min(k,num[u]);
		int nV = min(k,num[v]);
		num[u] += num[v];
		for(int j=0;j<=nU;++j) 
		{
			for(int t=0;t<=nV&&t+j<=k;++t)
			{
				dp[u][j+t] = min(1ll*dp[u][j+t],1ll*(k-t)*t*d+tree_u_v[j]+dp[v][t]); 
			}
		}
	}
}
int main()
{
	int n,m,x,y,d;
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<m;++i)
		scanf("%d",&x), good[x] = true;
	initEdge(); 
	for(int i=1;i<n;++i)
	{
		scanf("%d%d%d",&x,&y,&d);
		addedge(x,y,d);
		addedge(y,x,d);
	}
	memset(dp,0x3f,sizeof(dp));
	dfs(1,-1);
	printf("%d\n",dp[1][k]);
	
	return 0;
}

---

我爱树，我爱DP，我也爱LCA~