4539: [Hnoi2016]树

时间：2023-03-10 02:44:02
4539: [Hnoi2016]树

4539: [Hnoi2016]树

链接

分析：

　　主席树+倍增。

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

#define pa pair<int,int>

using namespace std;

typedef long long LL;

#define int LL

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = ;

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

struct OPT { int l, r, fa, rt; } q[N];

int head[N], dfn[N], st[N], ed[N], pos[N], fa[N][], siz[N], f[N][], g[N][], d1[N], d2[N];

set< pa > s;

int En, Index, NowIndex, n;

inline void add_edge(int u,int v) {

    ++En; e[En].to = v, e[En].nxt = head[u]; head[u] = En;

    ++En; e[En].to = u, e[En].nxt = head[v]; head[v] = En;

}

struct SegmentTree{

    int sum[N * ], ls[N * ], rs[N * ], Root[N], TreeIndex;

    void Insert(int l,int r,int &now,int pre,int p) {

        if (!now) now = ++TreeIndex;

        sum[now] = sum[pre] + ;

        if (l == r) return ;

        int mid = (l + r) >> ;

        if (p <= mid) {

            rs[now] = rs[pre];

            Insert(l, mid, ls[now], ls[pre], p);

        } else {

            ls[now] = ls[pre];

            Insert(mid + , r, rs[now], rs[pre], p);

        }

    }

    int query(int l,int r,int H,int T,int k) {

        if (l == r) return l;

        int mid = (l + r) >> ;

        if (k <= sum[ls[T]] - sum[ls[H]]) return query(l, mid, ls[H], ls[T], k);

        else return query(mid + , r, rs[H], rs[T], k - (sum[ls[T]] - sum[ls[H]]));

    }

}T;

void dfs(int u) {

    d1[u] = d1[fa[u][]] + ;

    st[u] = ++Index; pos[Index] = u; siz[u] = ;

    for (int i = ; i <= ; ++i) fa[u][i] = fa[fa[u][i - ]][i - ];

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

        int v = e[i].to;

        if (v == fa[u][]) continue;

        fa[v][] = u;

        dfs(v);

        siz[u] += siz[v];

    }

    ed[u] = Index;

}

int LCA1(int u,int v) {

    if (d1[u] < d1[v]) swap(u, v);

    int d = d1[u] - d1[v];

    for (int i = ; ~i; --i) if ((d >> i) & ) u = fa[u][i];

    if (u == v) return u;

    for (int i = ; ~i; --i) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];

    return fa[u][];

}

int getdis(int x,int y) {

    return d1[x] + d1[y] - d1[LCA1(x, y)] * ;

}

void add(int id) {

    int x = read(), y = read(), z;

    q[id].l = NowIndex, q[id].r = (NowIndex += siz[x]) - , q[id].rt = x;

    set< pa > :: iterator it = s.lower_bound(pa(y, )); z = q[it->second].rt;

    q[id].fa = T.query(, n, T.Root[st[z] - ], T.Root[ed[z]], y - q[it->second].l + );

    f[id][] = it->second, g[id][] = getdis(q[id].fa, z) + ;

    d2[id] = d2[it->second] + ;

    for (int i = ; i <= ; ++i) f[id][i] = f[f[id][i - ]][i - ], g[id][i] = g[id][i - ] + g[f[id][i - ]][i - ];

    s.insert(pa(q[id].r, id));

}

int LCA2(int u,int v,int tu,int tv) {

    if (d2[u] < d2[v]) swap(u, v), swap(tu, tv);

    int ans = , t = u, d = d2[u] - d2[v];

    for (int i = ; ~i; --i) if ((d >> i) & ) ans += g[u][i], u = f[u][i];

    if (u == v) {

        d --; ans = ; u = t;

        for (int i = ; ~i; --i) if ((d >> i) & ) ans += g[t][i], t = f[t][i];

        ans += getdis(q[t].fa, tv) +  + getdis(tu, q[u].rt);

        return ans;

    }

    ans += getdis(tu, q[t].rt) + getdis(tv, q[v].rt);

    for (int i = ; ~i; --i) if (f[u][i] != f[v][i]) ans += g[u][i] + g[v][i], u = f[u][i], v = f[v][i];

    ans += getdis(q[u].fa, q[v].fa) + ;

    return ans;

}

void Ask() {

    int u = read(), v = read(), ans, iu, iv, tu, tv;

    iu = s.lower_bound(pa(u, ))->second, iv = s.lower_bound(pa(v, ))->second;

    tu = T.query(, n, T.Root[st[q[iu].rt] - ], T.Root[ed[q[iu].rt]], u - q[iu].l + );

    tv = T.query(, n, T.Root[st[q[iv].rt] - ], T.Root[ed[q[iv].rt]], v - q[iv].l + );

    if (iu != iv) ans = LCA2(iu, iv, tu, tv);

    else ans = getdis(tu, tv);

    printf("%lld\n", ans);

}

signed main() {

    n = read();int m = read(), Q = read();

    for (int i = ; i < n; ++i) add_edge(read(), read());

    dfs();

    for (int i = ; i <= n; ++i)

        T.Insert(, n, T.Root[i], T.Root[i - ], pos[i]);

    NowIndex = n + ;

    s.insert(pa(n, )); q[].l = , q[].r = n, q[].rt = , q[].fa = ;

    for (int i = ; i <= m; ++i) add(i + );

    while (Q --) Ask();

    return ;

}

相关文章