B 开组会(可持久线段树+树剖) 武汉大学2023年新生程序设计竞赛（同步赛）

其实题目就是每次询问一个节点

在这个节点的基础上往下继续遍历t的深度，在这个遍历的过程中找一个最大值就行了 

其实这个题目数据非常水，直接暴力就可以过了

下面是别人过的代码

#include<bits/stdc++.h>
using namespace std;
const int mxn=5e5+10;
#define ll long long
ll n,m,a[mxn];
vector<ll> v[mxn];
ll dfs(int t,int x){ll ans=a[x];if(t==0) return ans;for(auto i:v[x])ans=max(dfs(t-1,i),ans);return ans;
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int x,y,i=1;i<n;i++)cin>>x>>y,v[x].push_back(y);cin>>m;for(int t,x,i=1;i<=m;i++){cin>>t>>x;cout<<dfs(t,x)<<"\n";}return 0;
}

但是我这还是说一下数据结构维护的做法

首先先dfs一次求dfn序，每个节点子树的sz，每个节点的深度dep

然后建一颗可持久化线段树

dep从1-n依次把每个点的权值插入到dfn序中，同时root维护的时当前dep插入完后头节点是啥

也就是在root[x]中已经把dep从1-x中的所有的值插入进去了

然后询问的时候询问在root[min(n, dep[x] + t)] 从dfn[x]到dfn[x] + sz[x] - 1

因为你最深的深度是min(n, dep[x] + t) 此时root已经把低于最深的深度的所以数都插入进去了

dfn序又帮你把询问的区间给确定了

using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f, N = 5e5 + 5, mod = 1e9 + 7;
int a[N];
vector<int>q[N], e[N];
int cnt, dep[N], dfn[N];
int sz[N];
void dfs(int x, int fa)
{dfn[x] = ++cnt;dep[x] = dep[fa] + 1;sz[x] = 1;for (auto w : q[x]) {if (w == fa) continue;dfs(w, x);sz[x] += sz[w];}
}
struct Tree
{int l, r, mx;
}tr[N*40];
int idx;
int build(int l, int r)
{int p = ++idx;if (l == r) return p;int mid = l + r >> 1;tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);return p;
}
void pushup(int p)
{tr[p].mx = max(tr[tr[p].l].mx, tr[tr[p].r].mx);
}
int insert(int p, int l, int r, int x,int val)
{int q = ++idx;tr[q] = tr[p];if (l == r) {tr[q].mx = val;return q;}int mid = l + r >> 1;if (x <= mid)  tr[q].l = insert(tr[p].l, l, mid, x, val);else tr[q].r = insert(tr[p].r, mid + 1, r, x, val);pushup(q);return q;
}
int root[N];
int ask(int p, int L, int R, int l, int r)
{if (l <= L && R <= r) {return tr[p].mx;}int mid = L + R >> 1;int mx = 0;if (l <= mid) mx = max(mx, ask(tr[p].l, L, mid, l, r));if (r > mid) mx = max(mx, ask(tr[p].r, mid + 1, R, l, r));return mx;
}
signed main()
{ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 1; i < n; i++) {int u, v;cin >> u >> v;q[u].push_back(v);q[v].push_back(u);}dfs(1, 0);for (int i = 1; i <= n; i++) {e[dep[i]].push_back(i);}root[0] = build(1, n);for (int i = 1; i <= n; i++) {int pre = 0;for (auto w : e[i]) {root[i] = insert(max(root[i - 1],pre), 1, n, dfn[w], a[w]);pre = root[i];}if (root[i] == 0) {root[i] = root[i - 1];}}int m;cin >> m;while (m--){int t, x;cin >> t >> x;cout << ask(root[min(n, dep[x] + t)], 1, n, dfn[x], dfn[x] + sz[x] - 1) << '\n';}
}