P1064 A 病毒官方题解

Gioush OJ · A 病毒 · 2026/08/18 00:00

【题意简述】

在一棵有根树上统计从每个非根节点出发、满足历史防疫限制并最终到达根的感染路线数。

【正解】

令 $f_x$ 表示从 $x$ 出发的合法路线数， $f_1=1$ ；令

pre(v)=\sum_{u\in path(1,v)}f_u.

固定起点 $x$ ，枚举子树内节点 $y$ ，表示先只向下扩散到 $y$ ，再第一次向上感染。沿 $x\to y$ 维护

U(x,y)=\min_{v\in path(x,y)}(d_v-h_v-1).

从 $y$ 上跳后的落点深度范围为

L=d_y-r_y,\qquad R=\min(d_y-l_y,U(x,y)).

若 $L\le R$ ，贡献是对应祖先路径上的 $\sum_{t=L}^{R}f_{\operatorname{anc}(y,t)}$ ，用 $pre$ 的路径前缀差在 $\mathcal O(1)$ 时间求出。对 $x$ 的整棵子树求和即得 $f_x$ 。

【正确性】

每条合法路线都存在唯一的“第一次向上感染”位置 $y$ 。上式精确枚举其所有合法落点；防疫限制由路径最小值 $U(x,y)$ 同时约束，故不会遗漏或重复。由于第一次上跳一定到达 $x$ 的严格祖先，按编号递增计算时所需状态均已求出。

【复杂度】

时间复杂度 $\mathcal O(n^2)$ ，空间复杂度 $\mathcal O(n)$ 。

【参考代码】

1/*2Author:Ehundategh3Date:2026/8/174Name:cancer.cpp5You steal,I kill.6*/7#include <vector>8#include <cstdio>9#include <cstring>10#include <algorithm>11#define MAXN 201012using namespace std;13const int Mod=998244353;14inline int Add(int a,int b){return a+b>=Mod?a+b-Mod:a+b;}15inline int Del(int a,int b){return a-b<0?a-b+Mod:a-b;}16int c,T,n,Fa[MAXN],Depth[MAXN],l[MAXN],r[MAXN],h[MAXN];17int Dp[MAXN],Pre[MAXN],Path[MAXN],Ans;18vector <int> Son[MAXN];19 20void DFS(int Now,int Limit){21    Path[Depth[Now]]=Now;22    Limit=min(Limit,Depth[Now]-h[Now]-1);23    int Left=Depth[Now]-r[Now];24    int Right=min(Depth[Now]-l[Now],Limit);25    if(Left<=Right){26        int Temp=Pre[Path[Right]];27        if(Left) Temp=Del(Temp,Pre[Path[Left-1]]);28        Ans=Add(Ans,Temp);29    }30    for(int i=0;i<(int)Son[Now].size();i++) DFS(Son[Now][i],Limit);31}32 33void Solve(){34    scanf("%d",&n);35    for(int i=1;i<=n;i++) Son[i].clear();36    Depth[1]=0;Dp[1]=Pre[1]=1;37    for(int i=2;i<=n;i++){38        scanf("%d%d%d%d",&Fa[i],&l[i],&r[i],&h[i]);39        Depth[i]=Depth[Fa[i]]+1;40        Son[Fa[i]].push_back(i);41    }42    for(int i=2;i<=n;i++){43        int Now=i;44        while(Now){Path[Depth[Now]]=Now;Now=Fa[Now];}45        Ans=0;DFS(i,n);46        Dp[i]=Ans;47        Pre[i]=Add(Pre[Fa[i]],Dp[i]);48    }49    for(int i=2;i<=n;i++) printf("%d%c",Dp[i]," \n"[i==n]);50}51 52int main(){53    scanf("%d%d",&c,&T);54    while(T-->0) Solve();55    return 0;56}