洛谷P3248 [HNOI2016]树(主席树 倍增 )

题意

题目链接

sol

从上午九点淦到现在qwq

思路比较简单，就是把每次加入的一坨点看成一个，然后直接倍增搞。。

然后慢慢调就可以了。。。

最后数量级会到达\(10^{10}\)，所以应该开long long

#include<bits/stdc++.h>
#define pair pair<ll, ll>
#define mp make_pair
#define fi first
#define se second
#define ll long long 
#define int long long  
using namespace std;
const int maxn = 1e5 + 10, b = 17, ss = 7e6 + 10;
inline ll read() {
    char c = getchar(); ll x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m, q;
vector<int> v[maxn];
int siz[maxn], top[maxn], son[maxn], fa[maxn], id[maxn], rev[maxn], tim;
ll dep[maxn];
void dfs1(int x, int _fa) {
    siz[x] = 1; dep[x] = dep[_fa] + 1; fa[x] = _fa;
    id[x] = ++tim; rev[tim] = x;
    for(auto &to : v[x]) {
        if(to == _fa) continue;
        dfs1(to, x);
        siz[x] += siz[to];
        if(siz[to] > siz[son[x]]) son[x] = to;
    }
}
void dfs2(int x, int topf) {
    top[x] = topf;
    if(!son[x]) return ;
    dfs2(son[x], topf);
    for(auto &to : v[x]) {
        if(top[to]) continue;
        dfs2(to, to);
    }
}
int lca(int x, int y) {
    while(top[x] ^ top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    if(dep[x] < dep[y]) swap(x, y);
    return y;
}
ll getdis(int x, int y) {
    int lca = lca(x, y);
    return dep[x] + dep[y] - 2 * dep[lca];
}
int tot;
struct ope {
    int l, r, id, fa, ti;//id所在的根节点是哪个，fa连到了大树哪个节点下面 ti第几次操作 
    bool operator < (const ope &rhs) const {
        return r < rhs.r;
    }
}md[maxn];
set<ope> lin;
int root[ss], si[ss], ls[ss], rs[ss], cnt;
void insert(int &k, int pre, int l, int r, int v) {
    k = ++cnt; ls[k] = ls[pre]; rs[k] = rs[pre]; si[k] = si[pre] + 1;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(v <= mid) insert(ls[k], ls[pre], l, mid, v);
    else insert(rs[k], rs[pre], mid + 1, r, v);
}
int query(int tl, int tr, int l, int r, int k) {
    if(l == r) return l;
    int cur = si[ls[tr]] - si[ls[tl]], mid = (l + r) >> 1;
    if(cur >= k) return query(ls[tl], ls[tr], l, mid, k);
    else return query(rs[tl], rs[tr], mid + 1, r, k - cur);
}
int kth(int x, int k) {//以x节点为根的子树中第k小的节点 
    int l = id[x], r = id[x] + siz[x] - 1;
    int tmp = query(root[l - 1], root[r], 1, n, k);
    //printf("%d %d %d\n", x, k, tmp);
    return tmp;
}
pair getid(int x) {//大树中编号为x节点对应的小树中的节点编号，以及该节点被加入的时间 
    ope nl = *lin.lower_bound((ope){0, x, 0, 0, 0});
    return {kth(nl.id, x - nl.l + 1), nl.ti};
}
vector<int> v[maxn];
int fa[maxn][b + 1];
ll dep[maxn], dis[maxn][b + 1], t[maxn][b + 1];
void dfs(int x, int fa) {
    dep[x] = dep[fa] + 1;
    for(auto &to : v[x]) {
        if(to == fa) continue;
        dfs(to, x);
    }
}
void pre() {
    for(int j = 1; j <= b; j++)
        for(int i = 1; i <= m; i++) {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
            t[i][j] = t[fa[i][j - 1]][j - 1];
            dis[i][j] = dis[i][j - 1] + dis[fa[i][j - 1]][j - 1];
        }
}
ll calc(int x) {//计算大树中编号为x的节点到所在大节点的根的距离 
    pair tmp = getid(x);
    return dep[tmp.fi] - dep[md[tmp.se].id];
}
ll query(ll x, ll y) {//大树中编号为x, y的节点的距离 
    pair bx = getid(x), by = getid(y);
    if(bx.se == by.se) return getdis(bx.fi, by.fi);
    ll prex = x, prey = y, gx, gy;
    x = bx.se; y = by.se; 
    if(dep[x] < dep[y]) swap(x, y), swap(prex, prey);
    ll ans = calc(prex);
    for(int i = b; ~i; i--)
        if(dep[fa[x][i]] >= dep[y]) {
            if(fa[x][i] == y) {
                gx = getid(t[x][i]).fi;
                gy = getid(prey).fi;
                return ans + dis[x][i] + getdis(gx, gy) - (dep[gx] - dep[md[fa[x][i]].id]);
            }
            ans += dis[x][i], x = fa[x][i];
        }
//  if(x == y) return ans - 2 * calc(prey); 
    for(int i = b; ~i; i--)
        if(fa[x][i] != fa[y][i]) {
            ans += dis[x][i]; ans += dis[y][i];
            x = fa[x][i], y = fa[y][i];
        }
    gx = getid(md[x].fa).fi, gy = getid(md[y].fa).fi;
    return ans + 2 + getdis(gx, gy) + calc(prey);
}
signed main() {
    //freopen("tree13.in", "r", stdin);freopen("b.out", "w", stdout);
    n = read(); m = read() + 1; q = read();
    for(int i = 1; i <= n - 1; i++) {
        int x = read(), y = read();
        v[x].push_back(y);
        v[y].push_back(x);
    }   
    dfs1(1, 0);
    dfs2(1, 1);//树剖 
    for(int i = 1; i <= n; i++) insert(root[i], root[i - 1], 1, n, rev[i]);
    md[1] = {1, siz[1], 1, 0, 1};
    lin.insert(md[1]);
    tot = siz[1] + 1;
    for(int i = 2; i <= m; i++) {
        int x = read(), to = read();
        md[i] = {tot, tot + siz[x] - 1, x, to, i};
        lin.insert(md[i]);
        tot += siz[x];
    }
    for(int i = 2; i <= m; i++) {
        ope x = md[i];
        int u = x.ti, v = getid(x.fa).se;//大树以操作次序来标号 
        v[v].push_back(u);
        dis[u][0] = dep[getid(md[u].fa).fi] - dep[md[v].id] + 1;
        fa[u][0] = v;
        t[u][0]  = md[u].fa;
    }
    dfs(1, 0);
    pre();
    
    while(q--) {
        ll x = read(), y = read();
        cout << query(x, y) << '\n';
    }
    return 0;   
}