#11 测试点莫名其妙 TLE
查看原帖
#11 测试点莫名其妙 TLE
90027
fanypcd楼主2022/1/8 13:48

RT,不知为何,感觉时间复杂度没问题

#include<bits/stdc++.h>
using namespace std;
#define ll long long
template <class T> inline void read(T &x)
{
	x = 0;
	int f = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		f |= ch == '-';
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + (ch - 48);
		ch = getchar();
	}
	x = f ? -x : x;
	return;
}
#define inf 0x3f3f3f3f
#define N 100005
struct Graph
{
	int first[N], Next[N << 1], to[N << 1], w[N << 1], tot;
	inline void add(int x, int y, int z)
	{
		Next[++tot] = first[x];
		first[x] = tot;
		to[tot] = y;
		w[tot] = z;
		return;
	}
};
Graph Ori, Vir;
int n, q;
int dfn[N], sign, dep[N], fa[N][21];
void dfs(int u, int pre)
{
	dfn[u] = ++sign;
	for(int i = 1; (1 << i) <= dep[u]; i++)
	{
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	}
	for(int i = Ori.first[u]; i; i = Ori.Next[i])
	{
		int v = Ori.to[i];
		if(v == pre)
		{
			continue;
		}
		dep[v] = dep[u] + 1;
		fa[v][0] = u;
		dfs(v, u);
	}
	return;
}
int lca(int x, int y)
{
	if(dep[x] > dep[y])
	{
		swap(x, y);
	}
	for(int i = 20; i >= 0; i--)
	{
		if(dep[fa[y][i]] >= dep[x])
		{
			y = fa[y][i];
		}
	}
	if(x == y)
	{
		return x;
	}
	for(int i = 20; i >= 0; i--)
	{
		if(fa[x][i] != fa[y][i])
		{
			x = fa[x][i], y = fa[y][i];
		}
	}
	return fa[x][0];
}
int a[N], st[N], top;
void build(int siz)
{
	Vir.tot = 0;
	st[top = 1] = 1;
	for(int i = 1; i <= siz; i++)
	{
		int now = a[i], lc = lca(st[top], now);
		while(1)
		{
			if(dep[lc] < dep[st[top - 1]])
			{
				Vir.add(st[top - 1], st[top], dep[st[top]] - dep[st[top - 1]]);
				top--;
			}
			else if(dep[lc] < dep[st[top]])
			{
				Vir.add(lc, st[top], dep[st[top]] - dep[lc]);
				top--;
			}
			else
			{
				break;
			}
		}
		if(st[top] != lc)
		{
			st[++top] = lc;
		}
		if(st[top] != now)
		{
			st[++top] = now;
		}
	}
	while(--top)
	{
		Vir.add(st[top], st[top + 1], dep[st[top + 1]] - dep[st[top]]);
	}
	return;
}
int col[N];
int f[N][2];
void dp(int u)
{
	int tmp0 = 0, tmp1 = 0, ch = 0;
	for(int i = Vir.first[u]; i; i = Vir.Next[i])
	{
		int v = Vir.to[i];
		dp(v);
		if((f[v][0] == inf && f[v][1] == inf) || (col[u] && col[v] && Vir.w[i] == 1))
		{
			f[u][0] = f[u][1] = inf;
			Vir.first[u] = 0;
			return;
		}
		if(f[v][0] <= f[v][1] + 1)
		{
			tmp0 += f[v][0];
		}
		else
		{
			ch++;
			tmp0 += f[v][1];
		}
		tmp1 += f[v][1];
	}
	if(!col[u])
	{
		f[u][0] = min(tmp1 + 1, tmp0 + ch);
		f[u][1] = tmp0 + ch - 1;
	}
	else
	{
		f[u][0] = inf;
		f[u][1] = tmp0 + ch;
	}
	Vir.first[u] = 0;
	return;
}
bool cmp(const int &a, const int &b)
{
	return dfn[a] < dfn[b];
}
signed main()
{
	read(n);
	int u, v;
	for(int i = 1; i < n; i++)
	{
		read(u), read(v);
		Ori.add(u, v, 0), Ori.add(v, u, 0);
	}
	dep[1] = 1;
	dfs(1, 0);
	read(q);
	int num;
	while(q--)
	{
		read(num);
		for(int i = 1; i <= num; i++)
		{
			read(a[i]);
			col[a[i]] = 1;
		}
		sort(a + 1, a + num + 1, cmp);
		build(num);
		dp(1);
		for(int i = 1; i <= num; i++)
		{
			col[a[i]] = 0;
		}
		int prtans = min(f[1][0], f[1][1]);
		printf("%d\n", prtans == inf ? -1 : prtans);
	}
	return 0;
}
2022/1/8 13:48
加载中...