『树的dfs序·线段树』某次模拟赛T2

本文主要是介绍『树的dfs序·线段树』某次模拟赛T2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$

$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

我们令$di{s}_x$表示节点$x$的到根的距离，令$ste{p}_x$表示节点x的深度。

那么对于每一对询问(x,k),我们令终止点为y，则我们要找的是：
$$\underset{k\le di{s}_y-di{s}_x}{\min }(ste{p}_y)$$

我们仔细关注条件$di{s}_y-di{s}_x\ge k$,也就是$di{s}_y\ge di{s}_x+k$.

我们每一次只需要在节点x的子树内，查找满足上述条件的最小$step$即可。

关键是如何快速查询呢？由于是子树问题，我们可以使用dfs序对应到区间上，如果我们能将所有满足条件$di{s}_y\ge di{s}_x+k$的子节点y，都将将对应的$ste{p}_y$放到对应的序列上，我们就可以用线段树来维护了。

那么我们可以将若干个询问离线处理，将权值从大到小排序。对于类型1加入权值$di{s}_x+k$,每一次查询的时候查询子树的最小$step$值；对于类型2，在对应位置上加入$step$值即可。

这个离线妙啊

$\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}$

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>using namespace std;
const int N = 8e5;int n, cnt(0);
int dis[N], step[N], L[N], R[N], Ans[N];
vector < pair<int, int> > G[N];
struct node{int type, point, val, id;friend bool operator < (node p1,node p2) {if (p1.val == p2.val) return p1.type > p2.type;return p1.val > p2.val;}
} ques[N * 2];
struct Segment {int l, r, min;
} a[N * 2];int read(void)
{int s = 0, w = 0; char c = getchar();while (c < '0' || c > '9') w |= c == '-', c = getchar();while (c >= '0' && c <= '9') s = s*10+c-48, c = getchar();return w ? -s : s;
}void dfs(int x,int fa)
{L[x] = ++ cnt;for (int i=0;i<G[x].size();++i){int y = G[x][i].first;int v = G[x][i].second;if (y == fa) continue;dis[y] = dis[x] + v;step[y] = step[x] + 1;dfs(y,x);		}R[x] = cnt;return;
}void build(int p,int l,int r)
{a[p].l = l, a[p].r = r, a[p].min = 1e9;if (l == r) return;int mid = l + r >> 1;build(p*2,l,mid);build(p*2+1,mid+1,r);return;
}void change(int p,int x,int v) 
{if (a[p].l == x && a[p].r == x) {a[p].min = min(a[p].min,v);return;}int mid = a[p].l + a[p].r >> 1;if (x <= mid) change(p*2,x,v);if (x > mid) change(p*2+1,x,v);a[p].min = min(a[p*2].min,a[p*2+1].min);return;
}int ask(int p,int l,int r)
{if (l <= a[p].l && r >= a[p].r) return a[p].min;int mid = a[p].l + a[p].r >> 1, ret = 1e9;if (l <= mid) ret = min(ret,ask(p*2,l,r));if (r > mid) ret = min(ret,ask(p*2+1,l,r));return ret;
}int main(void)
{freopen("b.in","r",stdin);freopen("b.out","w",stdout);read(), n = read();for (int i=1,x,y,v;i<n;++i){x = read(), y = read(), v = read();G[x].push_back({y,v});G[y].push_back({x,v});}dfs(1,0);int q = read();for (int i=1;i<=q;++i) {int x = read(), k = read();ques[i] = node{1,x,dis[x]+k,i};}for (int i=1;i<=n;++i) ques[q+i] = node{2,i,dis[i],0};sort(ques+1,ques+q+n+1);build(1,1,n);for (int i=1,ans;i<=q+n;++i){int type(ques[i].type), point(ques[i].point), Id(ques[i].id);if (type == 1)  Ans[Id] = ask(1,L[point],R[point])-step[point];else change(1,L[point],step[point]);}for (int i=1;i<=q;++i)printf("%d\n", Ans[i] > n ? -1 : Ans[i]);return 0;
}

这篇关于『树的dfs序·线段树』某次模拟赛T2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---