虚树板题 Wa on #11求调旋观
查看原帖
虚树板题 Wa on #11求调旋观
563650
haochengw920楼主2024/2/6 09:35

rt,为什么大家都 Wa on #11 呀

#include<cstdio>
#include<algorithm>
#define INF (0x3f3f3f3f)
using namespace std;
 
const int MAXN = 1000005;
 
int n, Q;
int K, p[MAXN], num;
int root;
bool mark[MAXN];
 
class Graph {
	private : 
	struct edge {
		int to, nex;
	}e[MAXN << 1]; int idx;
	public : 
	int head[MAXN];
	inline void add(int u, int v) {
		e[++ idx].to = v;
		e[idx].nex = head[u];
		head[u] = idx;
	}
	inline void add_edge(int u, int v) {
		add(u, v); add(v, u);
	}
	inline edge operator [] (const int &x) const {
		return e[x];
	}
	inline void Clear() {
		for (int i = 1; i <= idx; ++ i)
			e[i].nex = 0;
		idx = 0;
	}
}G, T;
 
namespace Tree_Init {
	int dep[MAXN], fa[MAXN][23];
	int cnt_dfn, dfn[MAXN];
	inline void Init_dfs(int u) {
		dfn[u] = ++ cnt_dfn;
		if (u == 1) dep[u] = 1;
		for (int i = 1; i <= 20; ++ i)
			fa[u][i] = fa[fa[u][i - 1]][i - 1];
		for (int i = G.head[u]; i; i = G[i].nex) {
			int v = G[i].to;
			if (v == fa[u][0]) continue;
			dep[v] = dep[u] + 1;
			fa[v][0] = u;
			Init_dfs(v);
		}
	}
	inline int Get_Lca(int u, int v) {
		if (dep[u] < dep[v]) swap(u, v);
		for (int i = 20; ~i; -- i) 
			if (dep[fa[u][i]] >= dep[v])
				u = fa[u][i];
		if (u == v) return u;
		for (int i = 20; ~i; -- i)
			if (fa[u][i] != fa[v][i])
				u = fa[u][i], v = fa[v][i];
		return fa[u][0];
	}
}
using namespace Tree_Init;
 
namespace Build_Virtua_tree {
	int top, stc[MAXN];
	inline bool cmp(const int &x, const int &y) {
		return dfn[x] < dfn[y];
	}
	inline int Build() {
		T.Clear();
		stc[top = 1] = p[1];
		int lca;
		for (int i = 2; i <= K; ++ i) {
			lca = Get_Lca(p[i], stc[top]);
			if (!mark[lca]) p[++ num] = lca;
			while (true) {
				if (dep[lca] >= dep[stc[top - 1]]) {
					if (lca != stc[top]) {
						T.add_edge(lca, stc[top]);
						if (lca != stc[top - 1])
							stc[top] = lca;
						else -- top;
					}
					break;
				} else{
					T.add_edge(stc[top], stc[top - 1]);
					-- top;
				}
			}
			stc[++ top] = p[i];
		}
		while (-- top) T.add_edge(stc[top], stc[top + 1]);
		return stc[1];
	}
}
using namespace Build_Virtua_tree;
 
inline int dfs(int u, int fath, int &fg) {
	int cts = 0, isd, res = 0;
	for (int i = T.head[u]; i; i = T[i].nex) {
		int v = T[i].to;
		if (v == fath) continue;
		isd = 0; res += dfs(v, u, isd);
		cts += (isd == 0);
	}
	if (mark[u]) return res + cts;
	if (cts <= 1) return res;
	return fg = 1, res + 1;
}
 
inline void Clear_() {
	for (int i = 1; i <= num; ++ i)
		mark[p[i]] = false, 
		T.head[p[i]] = 0;
}
 
int main()
{
	scanf ("%d", &n);
	for (int i = 1; i < n; ++ i) {
		int u, v; 
		scanf ("%d%d", &u, &v);
		G.add_edge(u, v);
	}
	Init_dfs(1);
	scanf ("%d", &Q);
	while (Q --) {
		scanf ("%d", &K);
		for (int i = 1; i <= K; ++ i)
			scanf ("%d", p + i), mark[p[i]] = true;
		sort(p + 1, p + K + 1, cmp);
		bool fg = false;
		for (int i = 1; i <= K; ++ i)
			if (mark[fa[p[i]][0]]) {
				fg = true;
				puts("-1");
				break;
			}
		if (fg) {
			Clear_();
			continue;
		}
		num = K;
		root = Build();
		int t = 0;
		printf ("%d\n", dfs(root, 0, t));
		Clear_();
	}
	return 0;
}
2024/2/6 09:35
加载中...