虚树板子,TLE on #8 求调,悬关
查看原帖
虚树板子,TLE on #8 求调,悬关
670046
___w楼主2024/2/28 16:58

rt

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define ll long long
#define space putchar(' ')
#define enter putchar('\n')
using namespace std;

inline int read() {
	int x = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9') f = c == '-' ? -1 : f, c = getchar();
	while (c >= '0' && c <= '9') x = (x<<3)+(x<<1)+(c^48), c = getchar();
	return x*f;
}

inline void write(int x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x/10);
	putchar('0'+x%10);
}

const int N = 1e5+5;
int n, m, q, idx, top, flag, a[N], s[N], v[N], f[N], g[N], d[N], fa[N][18], dfn[N];
vector <int> E[N], G[N];

void dfs(int x, int f) {
	dfn[x] = ++idx, d[x] = d[f]+1, fa[x][0] = f;
	for (int i = 1; i <= 17; ++i) fa[x][i] = fa[fa[x][i-1]][i-1];
	for (int y:E[x]) if (y != f) dfs(y, x);
}

int lca(int x, int y) {
	if (d[x] < d[y]) swap(x, y);
	for (int i = 17; ~i; --i) if (d[fa[x][i]] >= d[y]) x = fa[x][i];
	if (x == y) return x;
	for (int i = 17; ~i; --i) if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
	return fa[x][0];
}

bool cmp(int x, int y) { return dfn[x] < dfn[y]; }

void add(int x, int y) { G[x].pb(y), G[y].pb(x); }

void build() {
	sort(a+1, a+m+1, cmp); s[top = 1] = 1;
	for (int i = 1; i <= m; ++i) {
		if (a[i] == 1) continue;
		int l = lca(a[i], s[top]);
		if (l != s[top]) {
			while (dfn[l] < dfn[s[top-1]]) add(s[top-1], s[top]), --top;
			if (dfn[l] != dfn[s[top-1]]) add(l, s[top]), s[top] = l;
			else add(l, s[top--]);
		}
		s[++top] = a[i];
	}
	for (int i = 1; i < top; ++i) add(s[i], s[i+1]);
}

int dfs_(int x, int fa) {
	int res = 0, cnt = 0;
	for (int y:G[x]) if (y != fa) res += dfs_(y, x), cnt += g[y];
	if (v[x]) res += cnt, g[x] = 1;
	else if (cnt > 1) ++res;
	else g[x] = cnt;
	return res;
}

bool check(int x, int fa) {
	for (int y:E[x]) if (y != fa) {
		if (v[x] && v[y]) return 0;
		if (!check(y, x)) return 0;
	}
	return 1;
}

int main() {
	n = read();
	for (int i = 1; i < n; ++i) {
		int x = read(), y = read();
		E[x].pb(y), E[y].pb(x);
	}
	dfs(1, 0);
	q = read();
	while (q--) {
		for (int i = 1; i <= n; ++i) G[i].clear(), f[i] = g[i] = 0;
		for (int i = 1; i <= m; ++i) v[a[i]] = 0;
		m = read(), flag = 0;
		for (int i = 1; i <= m; ++i) a[i] = read(), v[a[i]] = 1;
		if (!check(1, 0)) { puts("-1"); continue; }
		build();
		write(dfs_(1, 0)), enter;
	}
	return 0;
}

record

2024/2/28 16:58
加载中...