牛客多校9.E.Eyjafjalla DFS序+树上倍增+主席树

牛客多校9.E.Eyjafjalla 😊 | Powered By HeartFireY

Problem Description

题目大意：给定一棵树，以及每个点的点权，保证根节点 1 1 1点权最大，离根节点越远点权越小。现在在一个节点 x x x出发，选取点权位于 [ l , r ] [l,r] [l,r]的在树上连续的点，最多可以选取多少个点。有多组询问。

首先分析题目：根据题目描述，对于任意一个非叶子节点而言，保证其子树所有点的点权全部小于其点权。那么对于感染温度范围 [ l , r ] [l, r] [l,r]，感染的过程我们可以抽象成以下模型：从某个点出发，找到小于等于 r r r的最远祖先，然后从该祖先开始向子树搜索满足大于等于 l l l​的节点个数。形象一点，如图所示：

从 x x x节点开始，向上找到满足小于等于 r r r的祖先节点 F F F，然后在 F F F的子树中搜索满足大于等于 l l l的节点个数。

那么分析我们解决问题的两个过程分别如何实现。

1. 寻找对于当前节点而言最远的满足条件的祖先：这个过程很简单，我们可以在跑 d f s dfs dfs序的过程中记录每个节点的所有祖先，然后对于每个节点遍历其全部祖先，然后找到符合要求的祖先即可。
2. 对于子树中寻找节点数的问题，我们可以使用主席树进行维护，按 d f s dfs dfs​​​​​​序建立主席树，然后查询子树中位于温度区间范围内的点的个数即可。

Accepted Code

#include 
using namespace std;

const int N = 1e3 + 10, maxn = 1e9 + 7;

int in[N], out[N], rk[N], fa[N][21], tot;
int root[N], ls[N > v;
        g[u].push_back(v), g[v].push_back(u);
    }
    for(int i = 1; i > val[i];
    dfs(1, 0);
    for(int i = 1; i > m;
    for(int i = 1, x, L, R; i > x >> L >> R;
        if(val[x] >= L && val[x]