Luogu P4197 Peaks

题目链接 \(Click\) \(Here\)

做法：\(Kruskal\)重构树上跑主席树

构造方法：把每条边拆出来成一个点，点权是原先的边权。每次连边的时候，连的不再是点，而是其原先点所在的联通块。

\(Kruskal\)重构树的性质：

二叉树
如果按最小生成树构造，则自顶到底权值递增（堆）
叶节点是原先的树上节点
两个在原图中可以经过权值\(<=k\)的边互相抵达的点，在最小生成树上也可以这样互相抵达，在\(Kruskal\)重构树上同理。

也就是说，假如一个点不能到比它的权值大的点，那么它能抵达的所有点就在它的子树里面。这个题目里我们从询问点跳到权值\(<=x\)中权值最大的点，其子树中的叶子节点，就是可以询问点可以通过点权\(<=x\)的点到达的所有点。

#include <bits/stdc++.h>

using namespace std;

const int N = 200010;

const int M = 500010;

int n, m, q, tot, INF, h[N], fa[N], val[N];

struct edge {int nxt, to;} e[N];

struct _edge {int u, v, w;}_e[M];

bool cmp (_edge lhs, _edge rhs) {

    return lhs.w < rhs.w;

}

int find (int x) {

    return x == fa[x] ? x : fa[x] = find (fa[x]);

}

int cnt, head[N];

void add_edge (int u, int v) {

    e[++cnt] = (edge) {head[u], v}; head[u] = cnt;

}

int rt[N];

#define mid ((l + r) >> 1)

struct Segment_Node {

    int sz, ls, rs;

}t[N << 5];

int modify (int _rt, int l, int r, int w) {

    int p = ++rt[0];

    t[p].sz = t[_rt].sz + 1;

    if (l != r) {

        if (w <= mid) {

            t[p].ls = modify (t[_rt].ls, l, mid, w), t[p].rs = t[_rt].rs;

        } else {

            t[p].rs = modify (t[_rt].rs, mid + 1, r, w), t[p].ls = t[_rt].ls;

        }

    } else {

        t[p].ls = t[p].rs = 0;

    }

    return p;

}

int sz[N], id[N], dfn[N], deep[N], fafa[N][20], totsize[N];

int sep[N];

int num (int x) {

    return lower_bound (sep + 1, sep + 1 + sep[0], x) - sep;

}

void dfs (int u, int _fa) {

    sz[u] = head[u] == 0;

	dfn[u] = ++dfn[0];

	totsize[u] = 1;

	id[dfn[0]] = u;

	fafa[u][0] = _fa;

    deep[u] = deep[_fa] + 1;

    rt[u] = modify (rt[id[dfn[u] - 1]], 1, INF, num (h[u])); //主席树维护高度

    for (int i = 1; (1 << i) <= deep[u]; ++i) {

        fafa[u][i] = fafa[fafa[u][i - 1]][i - 1];

    }

    for (int i = head[u]; i; i = e[i].nxt) {

        int v = e[i].to;

        if (v != _fa) {

            dfs (v, u);

            sz[u] += sz[v];

            totsize[u] += totsize[v];

        }

    }

}

int query (int u, int v, int l, int r, int k) {

    while (l < r) {

        int rch = t[t[v].rs].sz - t[t[u].rs].sz;

        if (k <= rch) {

            u = t[u].rs;

            v = t[v].rs;

            l = mid + 1;

        } else {

            u = t[u].ls;

            v = t[v].ls;

            k -= rch;

            r = mid;

        }

    }

    return l;

}

int read () {

	int s = 0, w = 1, ch = getchar ();

	while ('9' < ch || ch < '0') {

		if (ch == '-') w = -1;

		ch = getchar ();

	}

	while ('0' <= ch && ch <= '9') {

		s = (s << 1) + (s << 3) + ch - '0';

		ch = getchar ();

	}

	return s * w;

} 

int main () {

	memset (val, 0x3f, sizeof (val));

	tot = n = read (), m = read (), q = read ();

    t[0].sz = t[0].ls = t[0].rs = 0, sep[++sep[0]] = 0;

    for (int i = 1; i <= n; ++i) sep[++sep[0]] = h[i] = read ();

    for (int i = 1; i <= m; ++i) {

	    _e[i].u = read ();

	    _e[i].v = read ();

		_e[i].w = read ();

    }

    sort (_e + 1, _e + 1 + m, cmp);

    for (int i = 1; i <= n; ++i) fa[i] = i;

    for (int i = 1; i <= m; ++i) {

        int u = find (_e[i].u);

        int v = find (_e[i].v);

        if (u != v) {

            int T = ++tot;

            val[T] = _e[i].w;

            fa[u] = fa[v] = fa[T] = T;

            add_edge (T, u);

            add_edge (T, v);

        }

    }

    sort (sep + 1, sep + 1 + sep[0]);

    INF = sep[0] = unique (sep + 1, sep + 1 + sep[0]) - sep - 1;

    dfs (tot, 0);

	int lastans = 0;

    for (int i = 1; i <= q; ++i) {

        int u = read () ^ lastans;

		int x = read () ^ lastans;

		int k = read () ^ lastans;

        for (int j = 19; j >= 0; --j) {

			if (val[fafa[u][j]] <= x) {

                u = fafa[u][j];

            }

        }

        if (sz[u] < k) {

            puts ("-1");

			lastans = 0;

        } else {

			lastans = sep[query (rt[id[dfn[u] - 1]], rt[id[dfn[u] + totsize[u] - 1]], 1, INF, k)];

            printf ("%d\n", lastans);

        }

    }

}

巴特西

Luogu P4197 Peaks

题目链接 \(Click\) \(Here\)

最新文章

热门文章