题意:
对于一棵有n个节点,以1为根的树,树上节点分为重要节点和不重要节点,然后给出q个询问,每次询问给出不重要点的集合(大小为m),问树上关键点的数量。
关键点的定义(满足一条即可):
- 关键点为重要节点。
- 两个重要节点的LCA。
题解:
思维题,并不是想象中的数据结构/图论题。
因为一棵树有多组询问,对于每组询问,树的结构不会变。所以对于每个节点我们可以预处理出三个信息:
- depth:深度
- son:儿子的数量(即度数)
- father
然后对于每组询问,我们可以先把集合中的点按深度排序,先把答案记为ans=n-m。
然后从最深的点开始处理,若当前点u的son>2,即表示该点有两个子树,并且没有比该点更深的非重要点,所以该点的儿子都是重要点,即两个重要点的LCA,ans+1。
若当前点u的son=0,即表示u不能为其父亲提供重要点,所以son[father[u]]-1。
参考代码:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005 + 5;
int T, n, q;
struct EDGE
{
int v, nxt;
} edge[MAXN << 1];
int fir[MAXN], ecnt = 0;
void addedge(int u, int v)
{
edge[ecnt].v = v;
edge[ecnt].nxt = fir[u];
fir[u] = ecnt++;
}
int son[MAXN], fa[MAXN], depth[MAXN];
int so[MAXN], qu[MAXN];
bool cmp(int a, int b)
{
return depth[a] > depth[b];
}
void dfs(int u, int F)
{
fa[u] = F;
for (int i = fir[u]; i != -1; i = edge[i].nxt)
{
int v = edge[i].v;
if (depth[v] || v == F)
continue;
depth[v] = depth[u] + 1;
son[u]++;
dfs(v, u);
}
}
int main()
{
scanf("%d", &T);
int icase = 0;
while (T--)
{
scanf("%d%d", &n, &q);
ecnt = 0;
for (int i = 1; i <= n; i++)
{
fir[i] = -1;
son[i] = fa[i] = depth[i] = 0;
}
for (int i = 1; i <= n - 1; i++)
{
int u, v;
scanf("%d%d", &u, &v);
addedge(u, v), addedge(v, u);
}
depth[1] = 1;
dfs(1, -1);
printf("Case #%d:\n", ++icase);
while (q--)
{
int m;
scanf("%d", &m);
for (int i = 1; i <= m; i++)
scanf("%d", &qu[i]);
int ans = n - m;
sort(qu + 1, qu + 1 + m, cmp);
for (int i = 1; i <= m; i++)
so[qu[i]] = son[qu[i]];
for (int i = 1; i <= m; i++)
if (so[qu[i]] >= 2)
ans++;
else if (so[qu[i]] == 0)
so[fa[qu[i]]]--;
printf("%d\n", ans);
}
}
return 0;
}