[NOI2024] 登山

· · 题解

传送门

首先状态是简单的：f_x 表示从 x 出发到达山顶的方案数。

在题目的限制下显然是无后效性的。

做一个树上前缀和，设 y 到 x 路径上 d-h 的最小值为 k，则贡献是形如 g_{\min\{r_y,k\}}-g_{l_y} 的式子。

可以发现，从下往上做是相对容易的。

考虑从下往上做，再从上往下撤销。

当前 dfs 到一个位置，用并查集维护其子树内的点到这个点路径上 d-h 的最值。

具体地，y 到当前根的最值在 y 所在的集合的代表元处取到。

倍增预处理一个点上面第一个 d-h 小于这个点的位置，直接合并即可。

可以给每个点开个 vector，存储的信息形如 l_i,r_i,k_i，表示这个点的 dp 值等于 \sum k_i(g_{r_i}-g_{l_i-1})，这样方便直接撤销。

启发式合并即可做到 O(n\log n)。

还要特殊处理 l>r 的情况，对每个点倍增找到贡献为 0 的位置，直接打个 tag 即可。

总复杂度 O(n\log n)，数据结构仅需要用到并查集。

#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";
    }
}