欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-05-26 21:57:10
题意 "题目链接" Sol 从上午九点淦到现在qwq 思路比较简单,就是把每次加入的一坨点看成一个,然后直接倍增搞。。 然后慢慢调就可以了。。。 最后数量级会到达$10^{10}$,所以应该开long long cpp include define Pair pair define MP make_ ......

题意

题目链接

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;   
}