洛谷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; }
推荐阅读
-
洛谷P3248 [HNOI2016]树(主席树 倍增 )
-
洛谷P4197 Peaks(Kruskal重构树 主席树)
-
洛谷P4602 [CTSC2018]混合果汁(主席树)
-
洛谷P2468 [SDOI2010]粟粟的书架(二分答案 前缀和 主席树)
-
洛谷 - P4768 [NOI2018]归程(Kruskal重构树+树上倍增+最短路)
-
洛谷P3248 [HNOI2016]树(主席树 倍增 )
-
洛谷P4755 Beautiful Pair 笛卡尔树上启发式合并 主席树计数
-
洛谷 - P4755 Beautiful Pair(笛卡尔树+主席树)
-
洛谷 P4755 Beautiful Pair —— 主席树+笛卡尔树
-
洛谷4755 Beautiful Pair 分治 主席树 离散化