简单题目求条。
查看原帖
简单题目求条。
956129
z_z_b_楼主2025/1/16 20:30

rt,CF上wrong on test 4

#include<bits/stdc++.h>
#define int long long
using namespace std;
 
namespace io
{
	inline int read(){int x=0,w=0;char c=0;while(!isdigit(c))w|=c=='-',c=getchar();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();return w?-x:x;}
	template<typename T>inline void write(T x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');}
	template<typename T>inline void write_(T x){write(x),putchar(' ');}
	template<typename T>inline void writeln(T x){write(x),putchar('\n');}
}
using namespace io;
 
const int N=3e5+10;
int n,m,id,len,h[N],fa[N][25],dfn[N],dep[N];
vector<int> e[N],g[N];
int dp[N],f[N],mp[N],top,cnt,st[N]; 
 
void add(int u,int v){e[u].push_back(v),e[v].push_back(u);}
void add1(int u,int v){g[u].push_back(v),g[v].push_back(u);}
 
void dfs(int u,int f,int d)
{
	fa[u][0]=f,dfn[u]=++id,dep[u]=d;
	for(int i=1;i<=20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
	for(auto to:e[u]) if(to!=f) dfs(to,u,d+1);
}
 
int lca(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	for(int i=20;i>=0;i--)
		if(dep[fa[x][i]]>=dep[y]) x=fa[x][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[y][0];
}
 
void build()
{
	sort(h+1,h+m+1,[&](int x,int y){return dfn[x]<dfn[y];});
	st[top=1]=1;
	for(int i=1;i<=m;i++)
	{
		if(h[i]==1) continue;
		int l=lca(h[i],st[top]);
		if(l!=st[top])
		{
			while(dfn[st[top-1]]>dfn[l]) add1(st[top-1],st[top]),top--;
			if(l!=st[top-1]) add1(l,st[top]),st[top]=l;
			else add1(l,st[top--]);
		}
		st[++top]=h[i];
	}
	for(int i=1;i<top;i++) add1(st[i],st[i+1]);
}
 
void dfs1(int u,int fa)
{
	int sum=0;
	if(mp[u]) f[u]=1;
	for(auto to:g[u])
	{
		if(to==fa) continue;
		dfs1(to,u);
		dp[u]+=dp[to],sum+=f[to];
	}
	if(mp[u]) dp[u]+=sum;
	else if(sum==1) f[u]=1;
	else if(sum>1) dp[u]++;
	g[u].clear();
}
 
signed main()
{
	n=read();
	for(int i=1;i<n;i++) add(read(),read());
	dfs(1,0,1);
	int t=read();
	while(t--)
	{
		for(int i=1;i<=m;i++) mp[h[i]]=dp[h[i]]=f[h[i]]=0,h[i]=0;
		dp[1]=f[1]=id=cnt=0;
		m=read();
		for(int i=1;i<=m;i++) mp[h[i]=read()]=1;
		for(int i=1;i<=m;i++) if(mp[fa[h[i]][0]]) cnt=-1;
		build();
		dfs1(1,0);
		writeln(cnt==-1?-1:dp[1]);
	}
	return 0;
}
2025/1/16 20:30
加载中...