本文主要是介绍【虚树】世界树(金牌导航 虚树-1/luogu 3233),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
世界树
金牌导航 虚树-1
luogu 3233
题目大意
对于一棵树,给出若干询问,每个询问告诉你若干个特殊点,对于所有点,都会选择离自己最近(距离相等就选编号最小的)的特殊点,问对于所有特殊点,有多少个点选择该点
输入样例
10
2 1
3 2
4 3
5 4
6 1
7 3
8 3
9 4
10 1
5
2
6 1
5
2 7 3 6 9
1
8
4
8 7 10 3
5
2 9 3 5 8
输出样例
1 9
3 1 4 1 1
10
1 1 3 5
4 1 3 1 1
数据范围
1 ⩽ n , q , ∑ i = 1 q m i ⩽ 3 × 1 0 5 1\leqslant n,q,\sum_{i=1}^q m_i\leqslant 3\times 10^5 1⩽n,q,∑i=1qmi⩽3×105
解题思路
对于每次询问,建出相对的虚树
然后DP出虚树中每个点的离特殊点的最短距离
然后计算出分界点,得出每个特殊点会被多少点选择(这里只讲大概思路,详情见代码)
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 300100
#define INF 1e8
using namespace std;
int n, m, w, x, y, nn, num, tot, top, s[N], d[N], ss[N], faa[N], dep[N], val[N], ans[N], dfn[N], size[N], head[N], fa[N][30];
struct rec
{int to, next;
}a[N<<1];
struct node
{int s, v;
}f[N];
bool cmp(int a, int b)
{return dfn[a] < dfn[b];
}
void add(int x, int y)
{a[++tot].to = y;a[tot].next = head[x];head[x] = tot;
}
void dfs(int x)
{dfn[x] = ++w;//算dfs序size[x] = 1;for (int j = 1; j <= 18; ++j)fa[x][j] = fa[fa[x][j - 1]][j - 1];for (int i = head[x]; i; i = a[i].next)if (a[i].to != fa[x][0]){fa[a[i].to][0] = x;dep[a[i].to] = dep[x] + 1;dfs(a[i].to);size[x] += size[a[i].to];}
}
int lca(int x, int y)
{if (dep[x] < dep[y]) swap(x, y);for (int i = 18; i >= 0; --i)if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];for (int i = 18; i >= 0; --i)while(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];if (x != y){x = fa[x][0];y = fa[y][0];}return x;
}
void build()//建虚树
{top = 0;d[0] = 0;sort(s + 1, s + 1 + nn, cmp);num = nn;for (int i = 1; i <= nn; ++i){int u = s[i];if (!top){faa[u] = 0;d[++top] = u;}else{int g = lca(d[top], u);while(dep[d[top]] > dep[g]){if (dep[d[top - 1]] <= dep[g])faa[d[top]] = g;top--; }if (d[top] != g){faa[g] = d[top];f[g] = (node){INF, 0};d[++top] = g;s[++num] = g;}faa[u] = g;d[++top] = u;}}sort(s + 1, s + 1 + num, cmp);
}
int jump(int x, int y)//找第y辈祖先
{for (int i = 0; i <= 18; ++i, y >>= 1)if (y & 1) x = fa[x][i];return x;
}
void solve()
{for (int i = num; i > 1; --i)//自下而上求最短距离{int u = s[i], v = faa[u];if (f[u].s + dep[u] - dep[v] < f[v].s || f[u].s + dep[u] - dep[v] == f[v].s && f[u].v < f[v].v)f[v] = (node){f[u].s + dep[u] - dep[v], f[u].v};}for (int i = 2; i <= num; ++i)//自上而下,这样就求出了虚树上所有点到特殊点的最短路径{int u = s[i], v = faa[u];if (f[v].s + dep[u] - dep[v] < f[u].s || f[v].s + dep[u] - dep[v] == f[u].s && f[v].v < f[u].v)f[u] = (node){f[v].s + dep[u] - dep[v], f[v].v};}for (int i = 1; i <= num; ++i){int u = s[i], v = faa[u];val[u] = size[u];//子树中所有点都到该点,如果有更优解,那么再减if (i == 1){ans[f[u].v] += n - size[u];//dfs序最小的点上方所有点都到这个点(因为上方无关键点,所以是一条链,不存在其他子树)continue;}int son = jump(u, dep[u] - dep[v] - 1);//找到v的子树中u所在子树的根节点int S = size[son] - size[u];//求出之间的节点数val[v] -= size[son];//这一部分点暂时不选v(如果选那再加)if (f[u].v == f[v].v) ans[f[u].v] += S; //相等那之间的点选择一样else{int g = f[u].s - f[v].s + dep[u] + dep[v] + 1>> 1;//使分界点到两边的特殊点的长度一样if (f[v].v < f[u].v && f[u].s + dep[u] - g == f[v].s - dep[v] + g) g++;//如果两边长度一样选dfs序小的(注意这里如果分界点往u移动,那么到u的点-1,到v的点+1)g = size[jump(u, dep[u] - g)] - size[u];//求出到u的点个数ans[f[u].v] += g;ans[f[v].v] += S - g; }}for (int i = 1; i <= num; ++i)ans[f[s[i]].v] += val[s[i]];
}
int main()
{scanf("%d", &n);for (int i = 1; i < n; ++i){scanf("%d%d", &x, &y);add(x, y);add(y, x);}dep[1] = 1;dfs(1);scanf("%d", &m);while(m--){scanf("%d", &nn);for (int i = 1; i <= nn; ++i){scanf("%d", &s[i]);ss[i] = s[i];f[s[i]] = (node){0, s[i]};}memset(ans, 0, sizeof(ans));memset(val, 0, sizeof(val));build();solve();for (int i = 1; i <= nn; ++i)printf("%d ", ans[ss[i]]);putchar(10);}return 0;
}
这篇关于【虚树】世界树(金牌导航 虚树-1/luogu 3233)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!