专栏文章

题解：P11824 [湖北省选模拟 2025] 团队协作 / team

llittlez_meow
P11824题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipyvbr5
此快照首次捕获于
2025/12/03 20:11
3 个月前
此快照最后确认于
2025/12/03 20:11
3 个月前
查看原文

题意

对每个点求出包含这个点的所有独立集中点权最大值的和，对 998244353998244353 取模。

思路

我们称节点 ii 的点权比节点 jj 大当且仅当 vi>vjv_i>v_j 或 vi=vj,i>jv_i=v_j,i>j。
考虑转置原理。设 ai,ja_{i,j} 表示包含点 ii 且点权最大的点为 jj 的独立集个数，nn 阶方阵 A=(ai,j)A=(a_{i,j})，列向量 a⃗=[v1,v2,⋯ ,vn]⊤\vec{a}=[v_1,v_2,\cdots,v_n]^{\top}，则答案向量为 b⃗=Aa⃗\vec b=A\vec a。
它的转置问题即为：对于每个 ii，求满足 ii 是独立集中点权最大的点的所有独立集的点权和。
按点权从小到大加入每个点，加入点 ii 时所有独立集点权和的变化量就是 ii 的答案。在这里，一个点被加入指的是可以在独立集中出现，未被加入指的是不能出现在独立集中。
这是一个经典的 ddp 问题，我们使用静态 top tree 解决。对每个簇设 f(0/1,0/1),g(0/1,0/1)f(0/1,0/1),g(0/1,0/1) 分别表示不选/选上界点、不选/选下界点的独立集方案数和权值和，转移是显然的。值得注意的是，此处 g(1,∗)g(1,*) 我们不计入上界点的贡献。可以新建一个虚点 00 作为 11 的父亲方便统计答案。
如果把 ff 视为常量（矩阵里的量），则转移关于 gg 是线性的。
需要注意，你可以把 ddp 的每次修改看成持久化的，即我们修改的时候变量所占用的内存都是不同的，需要先赋值一次。
然后转置就行了。时间复杂度 O(nlog⁡n)O(n\log n)。发现我们实际上并不需要持久化，每次直接覆盖就行，所以空间 O(n)O(n)。如果还是不明白可以看代码，注释里标了转置前后的内容。
事实上，用转置原理得到的做法和其他几篇直接用 top tree 得到的做法是一样的。

代码

CPP
#include <bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
#define fi first
#define se second
using namespace std;
const int MAXN=3e5+2,MOD=998244353;
int n;
pair<int,int>val[MAXN];
int cnt;
struct Node{
	short type;//-1unit,0rake,1compress
	int up,dn,mid;
	int siz,lc,rc,fa;
	ll f[2][2],g[2][2];
	Node(const int&t=-1,const int&d=0,const int&e=0,const int&a=1,const int&b=0,const int&c=0){
		type=t,siz=a,lc=b,rc=c,up=d,dn=e,fa=0;
		memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
		return;
	}
}node[MAXN<<1];
bool isin[MAXN]; 
inline void upd(int now){
	Node&qwq(node[now]),&l(node[qwq.lc]),&r(node[qwq.rc]);
	memset(qwq.f,0,sizeof(qwq.f));
	if(node[now].type) F(i,0,1) F(j,0,1) F(k,0,isin[l.dn]) qwq.f[i][j]=(qwq.f[i][j]+l.f[i][k]*r.f[k][j])%MOD;
	else F(i,0,1) F(j,0,1) F(k,0,isin[r.dn]) qwq.f[i][j]=(qwq.f[i][j]+l.f[i][j]*r.f[i][k])%MOD;
	return;
}
inline void psd(int now){
	Node&qwq(node[now]),&l(node[qwq.lc]),&r(node[qwq.rc]);
	if(node[now].type){
		/*
		转置前 
		F(i,0,1) F(j,0,1) F(k,0,isin[l.dn]){
			qwq.g[i][j]=(qwq.g[i][j]+l.f[i][k]*r.g[k][j])%MOD;
			qwq.g[i][j]=(qwq.g[i][j]+l.g[i][k]*r.f[k][j])%MOD;
		}
		*/ 
		F(i,0,1) F(j,0,1) F(k,0,isin[l.dn]){
			r.g[k][j]=(r.g[k][j]+l.f[i][k]*qwq.g[i][j])%MOD;
			l.g[i][k]=(l.g[i][k]+r.f[k][j]*qwq.g[i][j])%MOD;
		}//倒不倒序不影响 
	}else{
		/*
		转置前 
		F(i,0,1) F(j,0,1) F(k,0,isin[r.dn]){
			qwq.g[i][j]=(qwq.g[i][j]+l.f[i][j]*r.g[i][k])%MOD;
			qwq.g[i][j]=(qwq.g[i][j]+l.g[i][j]*r.f[i][k])%MOD;
		}
		*/ 
		F(i,0,1) F(j,0,1) F(k,0,isin[r.dn]){
			r.g[i][k]=(r.g[i][k]+l.f[i][j]*qwq.g[i][j])%MOD;
			l.g[i][j]=(l.g[i][j]+r.f[i][k]*qwq.g[i][j])%MOD;
		}
	}
	memset(qwq.g,0,sizeof(qwq.g));
	return;
}
inline int merge(int x,int y,int type){
	node[x].fa=node[y].fa=++cnt;
	node[cnt]=Node(type,node[x].up,node[type?y:x].dn,node[x].siz+node[y].siz,x,y);
	return upd(cnt),cnt;
}
#define Poi vector<int>::iterator
int build(Poi l,Poi r,int type){
	if(l==r) return 0;
	if(l+1==r) return *l;
	int sum=0,all=0;
	for(auto it=l;it!=r;++it) all+=node[*it].siz;
	Poi mid=l+1;
	for(auto it=l;it!=r;++it){
		sum+=node[*it].siz;
		if(sum*2<=all) mid=it+1;
		else break;
	}
	return merge(build(l,mid,type),build(mid,r,type),type);
}
int siz[MAXN],fa[MAXN],son[MAXN],rt[MAXN];//根为 cnt 
vector<int>g[MAXN];
void dfs1(int now){
	siz[now]=1;
	node[now]=Node(-1,fa[now],now);
	node[now].f[0][0]=node[now].f[1][0]=node[now].f[0][1]=1;
	isin[now]=1;
	for(int i:g[now]){
		dfs1(i);
		siz[now]+=siz[i];
		if(siz[son[now]]<siz[i]) son[now]=i;
	}
	return;
}
void dfs2(int now,bool heavy){
	if(son[now]) dfs2(son[now],1);
	for(int i:g[now]) if(i!=son[now]) dfs2(i,0);
	if(!heavy){
		vector<int>chain;
		chain.push_back(now);
		for(int i(son[now]);i;i=son[i]){
			vector<int>sub({i});
			for(int j:g[fa[i]]) if(j!=i) sub.push_back(rt[j]);
			chain.push_back(build(sub.begin(),sub.end(),0));
		}
		rt[now]=build(chain.begin(),chain.end(),1);
	}
	return;
}
int ans[MAXN];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	F(i,2,n) cin>>fa[i],g[fa[i]].push_back(i);
	F(i,1,n) cin>>val[i].fi,val[i].se=i;
	sort(val+1,val+n+1);
	dfs1(1),cnt=n,dfs2(1,0);
	R(i,n,1){//倒序执行 
		/*
		转置前 (ans[i]-ans[i-1])+=node[cnt].g[0][0/1] 
		转置后倒序变成 node[cnt].g[0][0/1]+=val[i]-val[i+1] 
		*/
		node[cnt].g[0][0]=(node[cnt].g[0][0]+val[i].fi-val[i+1].fi+MOD)%MOD;
		if(isin[node[cnt].dn]) node[cnt].g[0][1]=(node[cnt].g[0][1]+val[i].fi-val[i+1].fi+MOD)%MOD;
		int now=val[i].se,tp=0;
		static int path[MAXN];
		while(node[now].fa) path[++tp]=node[now].fa,now=path[tp];
		R(j,tp,1) psd(path[j]);//从上到下倒序执行 
		now=val[i].se;
		ans[now]=node[now].g[0][1],node[now].g[0][1]=0;//node[now].g[0][1]=val[now]的转置 
		isin[now]=0,node[now].f[0][1]=0; 
		while(node[now].fa) upd(node[now].fa),now=node[now].fa;//按原顺序更新常量（矩阵里的量） 
	}
	F(i,1,n) cout<<ans[i]<<" "; 
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...