专栏文章

[NOI2024] 登山

__ANIG_
P10789题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@miqnuq2u
此快照首次捕获于
2025/12/04 07:51
3 个月前
此快照最后确认于
2025/12/04 07:51
3 个月前
查看原文
传送门
首先状态是简单的：fxf_x 表示从 xx 出发到达山顶的方案数。
在题目的限制下显然是无后效性的。
做一个树上前缀和，设 yy 到 xx 路径上 d−hd-h 的最小值为 kk，则贡献是形如 gmin⁡{ry,k}−glyg_{\min\{r_y,k\}}-g_{l_y} 的式子。
可以发现，从下往上做是相对容易的。
考虑从下往上做，再从上往下撤销。
当前 dfs 到一个位置，用并查集维护其子树内的点到这个点路径上 d−hd-h 的最值。
具体地，yy 到当前根的最值在 yy 所在的集合的代表元处取到。
倍增预处理一个点上面第一个 d−hd-h 小于这个点的位置，直接合并即可。
可以给每个点开个 vector，存储的信息形如 li,ri,kil_i,r_i,k_i，表示这个点的 dp 值等于 ∑ki(gri−gli−1)\sum k_i(g_{r_i}-g_{l_i-1})，这样方便直接撤销。
启发式合并即可做到 O(nlog⁡n)O(n\log n)。
还要特殊处理 l>rl>r 的情况，对每个点倍增找到贡献为 00 的位置，直接打个 tag 即可。
总复杂度 O(nlog⁡n)O(n\log n)，数据结构仅需要用到并查集。
CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5,mods=998244353;
int op,t,n,nw,fa[N],l[N],dy[N],r[N],mk[N],sm[N],sz[N],h[N],ff[N],d[N],f[N],dp[N],f1[N][20],f2[N][20];
vector<int>p[N],g[N],q[N],jl[N];
struct node{
	int l,r,op;
};
vector<node>fs[N];
int fd(int x){
	if(x==ff[x])return x;
	return ff[x]=fd(ff[x]);
}
void dfs(int x){
	for(int i=1;i<=18;i++){
		f1[x][i]=f1[f1[x][i-1]][i-1];
		f2[x][i]=min(f2[x][i-1],f2[f1[x][i-1]][i-1]);
	}
	h[x]=d[x]-h[x]-1;
	l[x]=d[x]-l[x];
	r[x]=d[x]-r[x];
	swap(l[x],r[x]);
	int y=x;
	for(int i=18;i>=0;i--)if(f2[y][i]>=h[x])y=f1[y][i];
	g[fa[y]].push_back(x);
	y=x;
	for(int i=18;i>=0;i--)if(f2[y][i]>=l[x])y=f1[y][i];
	if(h[x]>=l[x])jl[fa[y]].push_back(x);
	else jl[x].push_back(x);
	y=x;
	for(int i=18;i>=0;i--)if(f2[y][i]>=r[x])y=f1[y][i];
	if(h[x]>=r[x])q[fa[y]].push_back(x);
	else q[x].push_back(x);
	for(auto c:p[x]){
		d[c]=d[x]+1;
		f1[c][0]=x;
		f2[c][0]=h[x];
		dfs(c);
	}
}
void init(int x){
	for(auto c:p[x])init(c);
	sort(p[x].begin(),p[x].end(),[&](int a,int b){
	    return fs[a].size()>fs[b].size();
	});
	if(p[x].size())swap(fs[x],fs[p[x][0]]);
	for(int i=1;i<p[x].size();i++){
		int c=p[x][i];
		for(auto d:fs[c])fs[x].push_back(d),sm[x]++;
	}
	fs[x].push_back({l[x],r[x],1});
	sm[x]++;
	for(auto c:q[x]){
		fs[x].push_back({l[c],r[c],-1});
		fs[x].push_back({l[c],h[x],1});
		dy[c]=x;
		sz[x]++;
		sm[x]+=2;
	}
	for(auto c:jl[x]){
		fs[x].push_back({l[c],h[fd(dy[c])],-1});
		sz[fd(dy[c])]--;
		sm[x]++;
	}
	for(auto c:g[x]){
		fs[x].push_back({h[x]+1,h[c],-sz[c]});
		sz[x]+=sz[c];
		ff[c]=x;
		sm[x]++;
	}
}
int gets(int l,int r){
	if(l>nw)return 0;
	if(l>r)return 0;
	return dp[min(r,nw)]-dp[l-1];
}
void solve(int x,int res){
	if(mk[x])for(auto c:fs[x])res+=gets(c.l,c.r)*c.op,res%=mods;
	if(x!=1)f[x]=res;
	dp[d[x]]=(dp[d[x]-1]+f[x])%mods;
	nw=d[x];
	while(sm[x]--){
		auto c=fs[x].back();
		fs[x].pop_back();
		res-=gets(c.l,c.r)*c.op;
		res%=mods;
	}
    if(p[x].size()){
    	swap(fs[x],fs[p[x][0]]);
    	solve(p[x][0],res);
    	for(int i=1;i<p[x].size();i++){
    		int c=p[x][i];
    		mk[c]=1;
    		nw=d[x];
    		solve(c,0);
    	}
    }
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>op>>t;
	while(t--){
		memset(f,0,sizeof(f));
		memset(f1,0,sizeof(f1));
		memset(f2,0x3f,sizeof(f2));
		cin>>n;	
		for(int i=1;i<=n;i++)ff[i]=i,mk[i]=0,sm[i]=0,sz[i]=0,p[i].clear(),g[i].clear(),fs[i].clear(),q[i].clear(),jl[i].clear();
		for(int i=2;i<=n;i++){
			cin>>fa[i]>>l[i]>>r[i]>>h[i];
			p[fa[i]].push_back(i);
		}
		d[1]=1;
		dfs(1);
		init(1);
		f[1]=1;
		solve(1,0);
		for(int i=2;i<=n;i++)cout<<(f[i]%mods+mods)%mods<<" ";
		cout<<"\n";
	}
}

评论

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

正在加载评论...