我要评论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
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论