娄居吉勾
题目链接:YBT2023寒假Day10 C
题目大意
有一个 n 个点 m 条边的无向连通图,每个点至多在 k 个简单环上。
然后有 q 个操作,标记一个没有标记过的点,或者给你一个点求它得到所有标记点中距离最短的点的距离。
思路
如果 \(k=0\),就可以简单的点分树。
就建出来,然后对于每个子树维护里面所有点的标记点到根(重心)的最短距离。
修改的时候直接枚举点分数上到根的链,里面的每个点分别更改一下最短距离即可。
询问的时候,我们枚举这个点和标记点在点分树上的 LCA 的位置(也是枚举到根的链上的点),用到 LCA 的距离加 LCA 子树的最短距离即可。
(不用怕又走回自己的子树,因为边权非负肯定不优)
那这个时候不能用的问题是啥,就是它不一定经过 LCA 的位置。
那这条路径经过了什么,一定经过了链接 LCA 两个不同子树的非树边。
而且一个非树边可以确定一个简单环,所以这些边的数量是不超过 \(k\leqslant 10\) 的。
那我们在这些边的两端位置统计即可。
那对于多组询问,我们可以预处理出每个点作为 LCA 或者非树边两端点只走子树内带你到里面每个点的最短距离,并维护出每个点到它每个 LCA 再到标记点和这个 LCA 下的另一子树得到标记点的最短距离。
(其实两个可以说是实现上一样的)
然后就可以了。
代码
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N = 1e5 + 100;
struct node {
int to, nxt;
}e[N << 2];
int n, m, k, le[N], KK, sz[N], root, root_sum;
int fa[N], deg[N], dis[51][N], f[N];
queue <int> q;
bool in[N], ok[N];
void add(int x, int y) {
e[++KK] = (node){y, le[x]}; le[x] = KK;
}
void dfs0(int now) {
sz[now] = 1; in[now] = 1;
for (int i = le[now]; i; i = e[i].nxt)
if (!in[e[i].to] && !ok[e[i].to]) {
dfs0(e[i].to); sz[now] += sz[e[i].to];
}
}
void dfs1(int now, int father, int all) {
int sum = all - sz[now]; in[now] = 1;
for (int i = le[now]; i; i = e[i].nxt)
if (!in[e[i].to] && !ok[e[i].to]) {
dfs1(e[i].to, now, all); sum = max(sum, sz[e[i].to]);
}
if (sum < root_sum) root_sum = sum, root = now;
}
void slove(int fr, int d) {
while (!q.empty()) q.pop();
q.push(fr);
dis[d][fr] = 0;
while (!q.empty()) {
int now = q.front(); q.pop();
for (int i = le[now]; i; i = e[i].nxt)
if (!ok[e[i].to] && !dis[d][e[i].to] && e[i].to != fr) {
dis[d][e[i].to] = dis[d][now] + 1; q.push(e[i].to);
}
}
}
void clear(int now) {
in[now] = 0;
for (int i = le[now]; i; i = e[i].nxt)
if (!ok[e[i].to] && in[e[i].to]) {
clear(e[i].to);
}
}
void work(int now, int father) {
ok[now] = 1; fa[now] = father;
deg[now] = deg[father] + 1;
slove(now, deg[now]);
for (int i = le[now]; i; i = e[i].nxt)
if (!ok[e[i].to]) {
clear(e[i].to); dfs0(e[i].to); root_sum = sz[e[i].to] + 1; clear(e[i].to); dfs1(e[i].to, 0, sz[e[i].to]);
work(root, now);
}
}
void insert(int x) {
int now = x;
while (now) {
f[now] = min(f[now], dis[deg[now]][x]);
now = fa[now];
}
}
int query(int x) {
int now = x, re = INF;
while (now) {
re = min(re, f[now] + dis[deg[now]][x]);
now = fa[now];
}
return re;
}
int main() {
freopen("graph.in", "r", stdin);
freopen("graph.out", "w", stdout);
scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= m; i++) {
int x, y; scanf("%d %d", &x, &y);
add(x, y); add(y, x);
}
clear(1); dfs0(1); root_sum = n + 1; clear(1); dfs1(1, 0, sz[1]);
work(root, 0);
for (int i = 1; i <= n; i++) f[i] = INF;
int Q; scanf("%d", &Q);
while (Q--) {
int t, x;
scanf("%d %d", &t, &x);
if (t == 1) insert(x);
if (t == 2) printf("%d\n", query(x));
}
return 0;
}
标签:le,int,sum,YBT2023,娄居吉勾,Day10,LCA,now,void
From: https://www.cnblogs.com/Sakura-TJH/p/YBT2023Day10_C.html