中心城镇问题

题目描述

给出一个 \(n\) 个点的树，第 \(i\) 个点的权值是 \(a_i\)，现在要选择一些点建立据点，要求任意两个据点之间的距离必须大于 \(k\)，问选出据点的最大权值和是多少。

\(n\leq 10^6\)

解法

我发现我学不懂长链剖分的原因是指针基础为​零，而今天终于把我的心头大患解决了。

其实这题根本不需要任何题意转化，我们把两个据点的限制在 \(\tt lca\) 处考虑即可，那么可以直接掏出树形 \(dp\)，设 \(dp[u][i]\) 表示点 \(u\) 内最浅的据点离 \(u\) 的距离是 \(i\)，选出的最大权值和。转移考虑合并两棵子树，考虑最浅的点是再原来的子树中还是在新的子树中，我们枚举最浅点的距离 \(j(j\leq dep[v])\)，设 \(o=\max(j,k-j+1)\)，表示选取其他点的最小深度，这要求我们再求出 \(tmp[u][i]\) 表示 \(dp\) 数组的后缀最大值：

\[dp[u][j]\leftarrow \max(dp[v][j-1]+tmp[u][o],tmp[v][o-1]+dp[u][j]) \]

然后简单讲一下长链剖分需要用到的指针知识：*p 作为一个指针可以用 p=a 操作来指向数组的第一个元素，然后直接用 p[x] 就相当于取 *(p+x)，所以我们的 \(dp\) 数组就设置成一个指针数组即可，再根据深度设置指针的初始位置。

实现细节：\(dep[u]\) 代表子树 \(u\) 的长链长度，那么 \(dp[u]\) 范围是 \([0,dep[u])\)，转移时要注意卡好范围。

#include <cstdio>
#include <iostream>
using namespace std;
const int M = 1000005;
#define int long long
const int inf = 1e18;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,k,tot,f[M],a[M],son[M],dep[M],qwq[M<<1];
int *dp[M],*tmp[M];
struct edge {int v,next;}e[M<<1];
void upd(int &x,int y) {x=max(x,y);}
void pre(int u,int fa)
{
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==fa) continue;
		pre(v,u);
		if(dep[v]>dep[son[u]]) son[u]=v;
	}
	dep[u]=dep[son[u]]+1;
}
void dfs(int u,int fa)
{
	if(son[u])
	{
		dp[son[u]]=dp[u]+1;
		tmp[son[u]]=tmp[u]+1;
		dfs(son[u],u);
	}
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==fa || v==son[u]) continue;
		dp[v]=dp[u]+dep[u];
		tmp[v]=tmp[u]+dep[u];
		dfs(v,u);
		for(int j=dep[v];j;j--)
		{
			int o=max(j,k-j+1),t=-inf;
			//the min-dis lies in v
			if(o<dep[u]) upd(t,tmp[u][o]+dp[v][j-1]);
			else upd(t,dp[v][j-1]);//no assistance
			//the min-dis
			if(o<=dep[v]) upd(t,tmp[v][o-1]+dp[u][j]);
			else upd(t,dp[u][j]);//no assistance
			dp[u][j]=t;
		}
		for(int j=dep[v];j;j--)
		{
			tmp[u][j]=dp[u][j];
			if(j<dep[u]-1) upd(tmp[u][j],tmp[u][j+1]);
		}
	}
	dp[u][0]=a[u];
	if(k+1<dep[u]) dp[u][0]+=tmp[u][k+1];
	tmp[u][0]=dp[u][0];
	if(dep[u]>1) upd(tmp[u][0],tmp[u][1]);
}
signed main()
{
	freopen("central.in","r",stdin);
	freopen("central.out","w",stdout); 
	n=read();k=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		e[++tot]=edge{v,f[u]},f[u]=tot;
		e[++tot]=edge{u,f[v]},f[v]=tot;
	}
	dp[1]=qwq;tmp[1]=qwq+n+1;
	pre(1,0);dfs(1,0);
	printf("%lld\n",tmp[1][0]);
}

心理阴影

题目描述

给定一棵 \(n\) 个节点的有根树，现在有一个排列，满足若 \(u\) 是 \(v\) 的父节点则 \(u\) 在 \(v\) 之前，问这个排列逆序对的期望。

\(n\leq 4000\)

解法

有一个 \(O(n^5)\) 的算法可以拿到 \(50\) 分，就是你枚举两个点，然后用组合数加 \(dp\) 算贡献即可。

正解却是直接 \(dp\) 算贡献，考虑到逆序对是一个二元关系，那么我们同样也去设计二元关系的状态，设 \(dp[u][v]\) 表示把子树 \(u,v\) 合并之后 \(u,v\) 之间产生的期望逆序对数，转移考虑第一个位置是 \(u\) 还是 \(v\)：

\[f(u,v)=\frac{siz_u}{siz_u+siz_v}\cdot (\sum_{x\in son_u} f(x,v)+g(u,v))+\frac{siz_v}{siz_u+siz_v}\cdot(\sum_{x\in son_v} f(u,x)+g(v,u)) \]

其中 \(g(u,v)\) 表示子树 \(v\) 中比 \(u\) 小的数的个数，\(siz_u\) 表示子树 \(u\) 的大小，前面的系数就是考虑有 \(\frac{siz_u}{siz_u+siz_v}\) 的概率 \(u\) 放在第一位，因为这相当于从 \(siz_u+siz_v\) 个数中选出 \(siz_u\) 个，选到红色的概率。然后计算 \(u\) 和 子树 \(v\) 的贡献，就可以递归到子问题了，后面那部分的解释类似。

总状态数 \(O(n^2)\)，转移均摊 \(O(1)\)，所以时间复杂度 \(O(n^2)\)

总结

多想一下我再总结吧。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 4100;
const int MOD = 1e9+7;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,rt,tot,ans,f[M],fa[M];
int dp[M][M],inv[M],siz[M],g[M][M];
struct edge{int v,next;}e[M<<1];
void dfs(int u,int p)
{
	siz[u]=1;fa[u]=p;
	for(int i=u+1;i<=n;i++) g[i][u]++;
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==p) continue;
		dfs(v,u);siz[u]+=siz[v];
		for(int j=1;j<=n;j++) g[j][u]+=g[j][v];
	}
}
int get(int x,int y)
{
	if(~dp[x][y]) return dp[x][y];
	int res=(siz[x]*g[x][y]+siz[y]*g[y][x])%MOD;
	for(int i=f[x];i;i=e[i].next) if(e[i].v^fa[x])
		res=(res+siz[x]*get(e[i].v,y))%MOD;
	for(int i=f[y];i;i=e[i].next) if(e[i].v^fa[y])
		res=(res+siz[y]*get(x,e[i].v))%MOD;
	res=res*inv[siz[x]+siz[y]]%MOD;
	return dp[y][x]=dp[x][y]=res;
}
signed main()
{
	freopen("nightmare.in","r",stdin);
	freopen("nightmare.out","w",stdout); 
	n=read();rt=read();inv[0]=inv[1]=1;
	for(int i=2;i<=n;i++)
		inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		e[++tot]=edge{u,f[v]},f[v]=tot;
		e[++tot]=edge{v,f[u]},f[u]=tot;
	}
	memset(dp,-1,sizeof dp);
	dfs(rt,0);
	for(int i=1;i<=n;i++) ans+=g[i][i];
	for(int i=1;i<=n;i++)
	{
		for(int j=f[i];j;j=e[j].next)
		{
			int u=e[j].v;
			if(u==fa[i]) continue;
			for(int k=f[i];k;k=e[k].next)
			{
				int v=e[k].v;
				if(v==fa[i]) continue;
				if(u<v) ans=(ans+get(u,v))%MOD; 
			}
		}
	}
	printf("%lld\n",ans);
}