2020牛客暑期多校训练营（第一场）B Infinite Tree 虚树

https://blog.csdn.net/weixin_37517391/article/details/82744605

这里学习了虚树的建立。

https://blog.csdn.net/weixin_44282912/article/details/107346986

然后看了这篇blog，做出了这道题。

这道题如果n很小，比如n^2<=1e5,则可以直接建树，然后变成经典换根dp问题：选择一个源点，求出所有标记点到源点的距离乘标记点的点权和，最小。

但这题n<=1e5，显然无法建出完整的树。

我们发现：换根dp转移时：dp[y]=dp[x]+(f[1]-f[y]*2)*(dep[y]-dep[x]);， 与某个点子树的点权和有关，若x，y的f相同，则dp也相同。

所以我们就可以建立虚树：虚树是专门处理这种点较多，但关键点在可以接受的范围内的情况，关键点与他们的LCA是我们要处理的点。

我们建立虚树时按原树关键点的dfs序建立，这样只用考虑相邻两个点的lca即可。

这题我们强制要求1-i!,的路径边权从大到小(x与其儿子的边权为mindiv[y])，则1 - i！表示的点的dfs序刚好从小到大。

lca(i!,(i-1)!)可以用dep代替判断，相邻两个点的lca的dep与其中一个点相同，则lca一定是这个点。

而lca的dep可以用树状数组维护，(因为我们发现：从i-1 到i点，多乘了个i，而大于maxdiv[i]的边权是一样的，后面就开始分叉)

然后就是常规虚树的建立。

最后换根dp即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 4e5+7;
int head[M],cnt=1;
struct EDGE{int to,nxt,w;}ee[M*2];
void add(int x,int y){ee[++cnt].nxt=head[x],ee[cnt].to=y,head[x]=cnt;}

int n,w[M],mindiv[M];
int c[M];//树状数组 
int st[M],top; //模拟栈
int dep[M];//i!所在点的深度
int lcadep[M];//lca(i!,(i-1)!)所在点的深度
int tot;//虚树点的个数 
ll dp[M],f[M];//dp:u=i时的结果。  f：i的子树所有点w的和 

void pre()//预处理 
{
	int N=1e5;
	mindiv[1]=1;
	for(int i=2;i<=N;i++)//埃筛求mindiv 
	{
		if(mindiv[i])continue;
		for(int j=i;j<=N;j+=i)
		{
			if(mindiv[j])continue;
			mindiv[j]=i;
		}
	}
}

void up(int x,int d)
{
	while(x<=n)c[x]+=d,x+=(-x)&x;
}
int qu(int x)
{
	int ans=0;
	while(x)ans+=c[x],x-=(-x)&x;
	return ans;
}

void bd()//建立虚树
{
	dep[1]=0;
	for(int i=2;i<=n;i++)//预处理lcadep 
	{
		dep[i]=dep[i-1]+1;int j;
		for(j=i;j!=mindiv[j];j/=mindiv[j])dep[i]++;//此时的j就是maxdiv[i] 
		lcadep[i]=qu(n)-qu(j-1);//求sum{(maxdiv[j],n)} ,即从i与i-1，从maxdiv[i]往后(从大到小)的边都不在一条链上了 
		for(int j=i;j!=1;j/=mindiv[j])up(mindiv[j],1);//更新链上各类型边的个数 
	}
	st[1]=1;top=1;tot=n;
	for(int i=2;i<=n;i++)//虚树建立 
	{
		if(lcadep[i]==dep[st[top]]||top<=1)//i与i-1在同一条链上 
		{
			st[++top]=i;
			continue;
		}
		while(dep[st[top-1]]>=lcadep[i]&&top>1)add(st[top],st[top-1]),add(st[top-1],st[top]),top--;
		if(dep[st[top]]!=lcadep[i])//lca出现了 不是i!的点，new一个点，(每个i!最多new一个，所以虚树最多2*n个点) 
		{
			dep[++tot]=lcadep[i];
			add(st[top],tot),add(tot,st[top]);
			st[top]=tot;
		}
		st[++top]=i;
	}
	while(top>1)add(st[top],st[top-1]),add(st[top-1],st[top]),top--;//最后剩一条链 
}

void dfs(int x,int fa)//树形DP
{
	f[x]=w[x];
	dp[1]+=(ll)w[x]*dep[x];//dp[1]即u=1的时，题目式子的结果 
	for(int i=head[x];i;i=ee[i].nxt)
	{
		int y=ee[i].to;
		if(y==fa)continue;
		dfs(y,x);
		f[x]+=f[y];
	//	dp[x]+=dp[y]+f[y]*(dep[y]-dep[x]);//以x为根的子树，到x点距离*w[i] 的结果
	}
} 
void gao(int x,int fa)//换根DP 
{
	for(int i=head[x];i;i=ee[i].nxt)
	{
		int y=ee[i].to;
		if(y==fa)continue;
		dp[y]=dp[x]+(f[1]-f[y]*2)*(dep[y]-dep[x]);
	//	cout<<y<<" -   "<<dp[y]<<endl;
		gao(y,x);
	}
}
void init()//初始化 
{
	for(int i=0;i<=2*n;i++)head[i]=c[i]=w[i]=0;//不要忘了w初始化为0 
	cnt=1;
}

int main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.ans","w",stdout);
	pre();
	while(~scanf("%d",&n))
	{
		init();
		for(int i=1;i<=n;i++)scanf("%d",&w[i]);
		bd();
		dp[1]=0;
		dfs(1,0);
		gao(1,0);
		ll ans=dp[1];
		for(int i=1;i<=tot;i++)ans=min(ans,dp[i]);
		printf("%lld\n",ans);
	}
	return 0;
}

 

本文地址：https://blog.csdn.net/bjfu170203101/article/details/108186755