求助,为啥虚树模板题会TLEa
查看原帖
求助,为啥虚树模板题会TLEa
139012
wrpwrp楼主2020/7/24 19:42
#pragma GCC optimize(2)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define R register
#define LL long long
const int inf = 0x3f3f3f3f;
const int N = 4e5 + 10;

inline int read() {
	char a = getchar(); int x = 0,f = 1;
	for(; a>'9' ||  a<'0'; a = getchar()) if(a == '-') f = -1;
	for(;a >= '0' && a <= '9'; a = getchar()) x = x * 10 + a - '0';
	return x * f;
}

int n, pn, dfn[N], test;
struct Tree1 {
	struct edge { int to, next; } e[N << 1];
	int head[N], cnt;
	inline void add(int x, int y) { e[++ cnt] = {y, head[x] }; head[x] = cnt; }
	int dep[N], fa[N], top[N], siz[N], son[N];
	int num = 0;
	inline void dfs1(int x, int fx) {
		dep[x] = dep[fx] + 1; fa[x] = fx; siz[x] = 1;
		dfn[x] = ++ num;
		for(R int i = head[x]; i; i = e[i].next) {
			int y = e[i].to; 
			if(y == fx) continue;
			dfs1(y, x);
			if(siz[y] > siz[son[x]]) son[x] = y;
		}
	}
	inline void dfs2(int x, int topx) {
		top[x] = topx;
		if(son[x]) dfs2(son[x], topx);
		for(R int i = head[x]; i; i = e[i].next) {
			int y = e[i].to;
			if(y == fa[x] || y == son[x]) continue;
			dfs2(y, y);
		}
	}
	inline int lca(int x, int y) {
		while(top[x] != top[y]) {
			if(dep[top[x]] > dep[top[y]]) x = fa[top[x]];
			else y = fa[top[y]];
		}
		return dep[x] < dep[y] ? x : y;
	}
}G;

int ok[N];
struct Tree2 {
	struct edge { int to, next; } e[N << 1];
	int head[N], cnt, dp[N], g[N];
	int stk[N << 1], top; int f = 0;
	inline void begin() {
		while(top) { head[stk[top]] = 0; top --; }
		cnt = 0; f = 0;
	}
	inline void Add(int x, int y) { e[++ cnt] = {y, head[x] }; head[x] = cnt; }
	inline void add(int x, int y) { 
	//	cout << x << ' ' << y << endl;
		stk[++ top] = x; stk[++ top] = y;
		if((G.fa[x] == y || G.fa[y] == x) && ok[x] == test && ok[y] == test) f = 1;
		Add(x, y); Add(y, x); dp[x] = dp[y] = 0; g[x] = g[y] = 0;
	}
	inline void dfs(int x, int fx) {
		if(ok[x] == test) { g[x] = 1;  } 
		int sum = 0;
		for(R int i = head[x]; i; i = e[i].next) {
			int y = e[i].to; if(y == fx) continue;
			dfs(y, x); sum += g[y];
		}
		if( g[x] ) {
			for(R int i = head[x]; i; i = e[i].next) {
				int y = e[i].to; if(y == fx) continue;
				dp[x] += dp[y] + g[y];
			}
			return ;
		}
		if( sum <= 1) {
			for(R int i = head[x]; i; i = e[i].next) {
				int y = e[i].to; if(y == fx) continue;
				dp[x] += dp[y];
			}
			g[x] = sum;
			return ;
		}
		if( sum > 1) {
			for(R int i = head[x]; i; i = e[i].next) {
				int y = e[i].to; if(y == fx) continue;
				dp[x] += dp[y];
			}
			dp[x] ++; g[x] = 0;
		}
	}
	inline void solve() {
		if(f) { printf("-1\n"); return ;}
		
		dfs(1, 0);
		printf("%d\n", dp[1]);
	}
}XG;
int a[N];

inline bool cmp(int a, int b) { return dfn[a] < dfn[b]; }
int stk[N], top;

int main() {
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	n = read();
	for(R int i = 1; i < n; i ++) {
		int x = read(), y = read();
		G.add(x, y); G.add(y, x);
	}
	G.dfs1(1, 0); G.dfs2(1, 1);	
	//cout << G.lca(6, 2) << endl;
	int m = read();
	while(m --) {
		pn = read(); test ++;
		for(R int i = 1; i <= pn; i ++) a[i] = read(), ok[a[i]] = test; 
		sort(a + 1, a + 1 + pn); pn = unique(a + 1, a + 1 + pn) - a - 1;
		sort(a + 1, a + 1 + pn, cmp);
		//for(R int i = 1; i <= pn; i ++) cout << dfn[a[i]] <<' ';
		stk[top = 1] = 1; XG.begin();
		for(R int i = 1; i <= pn; i ++) {
			if(a[i] == 1) continue;
			int l = G.lca(stk[top], a[i]);
			while(G.dep[stk[top - 1]] > G.dep[l]) {
				XG.add(stk[top - 1], stk[top]); top --;
			}
			if(stk[top] != l) {
				if(stk[top - 1] == l) { XG.add(stk[top - 1], stk[top]); top --; }
				else XG.add(l, stk[top]), stk[top] = l;
			}
			stk[++ top]= a[i];
		}
		while(top > 1) { XG.add(stk[top - 1], stk[top]); top --; }
		XG.solve();
	}
	return 0;	
}
2020/7/24 19:42
加载中...