DreamOJ D10009
标签
DP 线段树 均摊
题意
给定一个包含 \(n\) 个节点根为 \(1\) 的树，和一个序列 \(s\) 。
如果满足以下两个条件，那么一个包含 \(k\) 条简单路径的可重集合认为是合法的。
- 这个可重集合中所有的路径都是从根节点 \(1\) 出发。
- 令 \(c_i\) 为覆盖节点 \(i\) 的路径数量，如果对于每对拥有相同父亲节点的节点 \((u,v)\) ，要求 \(|c_u-c_v| \leq 1\) 。
对于这个可重集合，其权值为 \(\sum_{i=1}^n c_is_i\) 。
可以证明，每组数据至少有一个可用的路径集合，请你找到所有合法的可重集合中的最大权值。
题解
正解1
首先，由于 \(s[i]\ge0\) 所以，可重集中的路径一定是越长越好的。我们不难证明，可重集中的每一条路径都是一条由1号节点到某个叶子节点的路径。
故一个相对暴力的做法就产生了：
我们对于每个节点动态开一个线段树，维护其所有儿子到其子树内叶子节点的最大权值。
接着用最大权值加上该节点本身的权值，转递给父节点建树。
对于每一次从根节点找路径的过程，我们从找到的叶子节点向上更新，把当前节点的贡献在父节点线段树中的位置赋为一个极小值，再递归父节点。这是为了在保证 \(|c_u-c_v| \leq 1\) 的情况下，每次找路径选择的都是被选择次数最少的子节点的贡献。当我们发现某个节点的线段树找出来的最大值是极小值时，这就意味着它的所有子节点的贡献都已经被选了一次，所以我们暴力重构该节点的线段树。
这样的复杂度直接与 \(k\) 挂钩，由于 \(k\) 很大，复杂度显然爆炸。考虑缩小 \(k\) 范围，由于每次找路径都是在子节点中轮流找路径，故不是每次找路径都要浪费线段树来暴力找。初始时，我们认为需要从1号节点找 \(k\) 条路径。我们遍历整棵树，把 \(k\div son\) 的次数交给子节点去找，视为一个子问题，该节点仅查找 \(k\%son\) 条路径（\(son\) 表示节点的儿子数量）。由于叶子节点无需继续查找，每个非叶子节点最多查儿子个数次路径，总次数与 \(n\) 同阶。然而重构操作仍然需要，比较难写。复杂度可以近似为 \(O(logn\times \sum_{i=1}^n son[i]\times d[i])\)（\(son[i]\) 表示儿子数量，\(d[i]\) 为节点深度）。根据yd所说，由于 \(son[i]\) 与 \(d[i]\) 成反比，总复杂度似乎可以均摊成正确的 \(O(nlogn)\)。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int T,n,k,a[N],b[N],pl[N],fa[N],ans,d[N];
vector<int>edge[N];
struct TREE{
int mx,wch;
};
struct node{
int siz;
vector<int>us1,us2;
int lson(int l,int r)
{
return (l+r)/2;
}
int rson(int l,int r)
{
return (l+r)/2+1;
}
TREE update(TREE x,TREE y)
{
if(x.mx<y.mx)
return y;
else
return x;
}
void pushup(int x)
{
if(tree[x*2].mx>tree[x*2+1].mx)
tree[x]=tree[x*2];
else
tree[x]=tree[x*2+1];
return;
}
void build(int l,int r,int x)
{
if(l>r)
return;
if(l==r)
{
tree[x]=TREE{us1[l],us2[l]};
return;
}
build(l,lson(l,r),x*2);
build(rson(l,r),r,x*2+1);
pushup(x);
return;
}
void change(int l,int r,int x,int to,TREE w)
{
if(l==r)
{
tree[x]=w;
return;
}
if(lson(l,r)>=to)
change(l,lson(l,r),x*2,to,w);
else
change(rson(l,r),r,x*2+1,to,w);
pushup(x);
return;
}
vector<TREE>tree;
}t[N];
void dfs(int x)
{
if(edge[x].size()==0)
return;
int w=b[x]/edge[x].size();
b[x]%=edge[x].size();
t[x].siz=edge[x].size();
t[x].tree.resize(edge[x].size()*4+10);
vector<int>us1(edge[x].size()+10);
vector<int>us2(edge[x].size()+10);
for(int i=0;i<edge[x].size();i++)
{
int to=edge[x][i];
d[to]=d[x]+1;
b[to]+=w;
dfs(to);
pl[to]=i+1;
if(edge[to].size()==0)
{
us1[i+1]=a[to];
us2[i+1]=to;
}
else
{
TREE xx=t[to].tree[1];
us1[i+1]=a[to]+xx.mx;
us2[i+1]=xx.wch;
}
}
t[x].us1=us1;
t[x].us2=us2;
t[x].build(1,t[x].siz,1);
return;
}
void check(int x)
{
vector<int>us1(edge[x].size()+10);
vector<int>us2(edge[x].size()+10);
if(t[x].tree[1].mx==INT_MIN)
{
for(int i=0;i<edge[x].size();i++)
{
int to=edge[x][i];
if(edge[to].size()==0)
{
us1[i+1]=a[to];
us2[i+1]=to;
}
else
{
TREE xx=t[to].tree[1];
us1[i+1]=a[to]+xx.mx;
us2[i+1]=xx.wch;
}
}
t[x].us1=us1;
t[x].us2=us2;
t[x].build(1,t[x].siz,1);
}
return;
}
void getnw(int st,int ed)
{
if(d[fa[st]]>=d[ed])
t[fa[st]].change(1,t[fa[st]].siz,1,pl[st],TREE{INT_MIN,0});
else
t[fa[st]].change(1,t[fa[st]].siz,1,pl[st],TREE{t[st].tree[1].mx+a[st],t[st].tree[1].wch});
check(fa[st]);
if(fa[st]!=1)
getnw(fa[st],ed);
return;
}
void dfs2(int x)
{
for(int i=0;i<edge[x].size();i++)
{
int to=edge[x][i];
dfs2(to);
}
if(edge[x].size()!=0)
{
for(int i=1;i<=b[x];i++)
{
TREE us=t[x].tree[1];
b[us.wch]++;
getnw(us.wch,x);
}
b[x]=0;
}
return;
}
void dfs3(int x)
{
for(int i=0;i<edge[x].size();i++)
{
int to=edge[x][i];
dfs3(to);
b[x]+=b[to];
}
ans+=b[x]*a[x];
return;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>T;
while(T--)
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
b[i]=0;
edge[i].clear();
}
for(int i=2;i<=n;i++)
{
cin>>fa[i];
edge[fa[i]].push_back(i);
}
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
b[1]=k;
dfs(1);
dfs2(1);
ans=0;
dfs3(1);
cout<<ans<<'\n';
}
return 0;
}
可能的出错点
出错点挺多，如果要写建议看看我的代码。
1.要开long long。
2.注意全局变量与局部变量。
3.注意update部分的细节。