未过样例求条
查看原帖
未过样例求条
826774
Little_Fox_Fairy楼主2024/10/19 11:34

写了一亿年了。

//在太阳西斜的这个世界里,置身天上之森,等这场战争结束之后,不归之人与望眼欲穿的人们,人人本着正义之名,长存不灭的过去,逐渐消逝的未来,我回来了,纵使日薄西山,即使看不到未来,此时此刻的光辉,盼君勿忘.
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
namespace fast_IO {
#define IOSIZE 100000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
const int N=2e5+10;
const int INF=0x3f3f3f3f;

int n,m,h[N],rt;
int vis[N],col[N],tr[N];
int without[N],ans[N];
vector<int> e[N];
vector<int> g[N];
namespace Top_Tree {
	int dep[N],siz[N],top[N],fa[N],tim,son[N],dis[N],dfn[N];
	inline void dfs(int u,int f=0) {
		dep[u]=dep[f]+1,siz[u]=1,fa[u]=f,dfn[u]=++tim;
		for (auto j : e[u]) {
			int v=j;
			if (v==f) continue;
			dfs(v,u);
			siz[u]+=siz[v];
			if (siz[v]>siz[son[u]]) son[u]=v;
		}
		return ;
	}
	inline void df5(int u,int tp) {
		top[u]=tp;
		if (!son[u]) return ;
		df5(son[u],tp);
		for (auto j : e[u]) {
			int v=j;
			if (v==son[u] or v==fa[u]) continue;
			df5(v,v);
		}
		return ;
	}
	inline void build() {
		dfs(1),df5(1,1);
		return ;
	}
	inline int calc_LCA(int u,int v) {
		while (top[u]!=top[v]) {
			if (dep[top[u]]<dep[top[v]]) swap(u,v);
			u=fa[top[u]];
		}
		return (dep[u]<dep[v]?u:v);
	}
	inline int calc_dist(int u,int v) {
		int LCA=calc_LCA(u,v);
		return dep[u]+dep[v]-2*dep[LCA];
	}
}
namespace Lowest_Common_Ancestor {
	int f[N][25],dep[N];
	inline void init(int u,int fa=0) {
		dep[u]=dep[fa]+1;
		f[u][0]=fa;
		for (int i=1;i<=20;i++) f[u][i]=f[f[u][i-1]][i-1];
		for (auto v : e[u]) if (v!=fa) init(v,u);
		return ;
	}
	inline void build() {
		init(1);
		return ;
	}
}
using Top_Tree::dfn;
using Top_Tree::calc_LCA;
using Top_Tree::dep;
using Top_Tree::calc_dist;
using Top_Tree::siz;
using Lowest_Common_Ancestor::f;
inline void add(int u,int v) {
	e[u].emplace_back(v);
	return ;
}
inline void dfs(int u,int fa) {
	col[u]=u*vis[u];
	for (auto j : g[u]) {
		int v=j;
		if (v==fa) continue;
		dfs(v,u);
		int dist1=dep[col[v]]-dep[u],dist2=col[u]?dep[col[u]]-dep[u]:INF;
		if (dist1<dist2 or (dist1==dist2 and col[v]<col[u])) col[u]=col[v];
	}
	return ;
}
inline void df5(int u,int fa) {
	for (auto j : g[u]) {
		int v=j;
		if (v==fa) continue;
		int dist1=calc_dist(col[u],v),dist2=calc_dist(col[v],v);
		if (dist1<dist2 or (dist1==dist2 and col[u]<col[v])) col[v]=col[u];
		df5(v,u);
	}
	return ;
}
inline void dfz(int u,int fa) {
	without[u]=siz[u];
	for (auto j : g[u]) {
		int v=j;
		if (v==fa) continue;
		dfz(v,u);int s,mid;s=mid=v;
		for (int i=20;i>=0;i--) if (dep[f[s][i]]>dep[u]) s=f[s][i];
		without[u]-=siz[s];
		if (col[u]==col[v]) {
			ans[col[u]]+=siz[s]-siz[v];
		}
		else {
			for (int i=20;i>=0;i--) {
				if (dep[f[mid][i]]<=dep[u]) continue;
				int dist1=calc_dist(col[u],f[mid][i]),dist2=calc_dist(col[v],f[mid][i]);
				if (dist1<dist2 or (dist1==dist2 and col[v]<col[u])) mid=f[mid][i];
			}
			ans[col[u]]+=siz[s]-siz[mid];
			ans[col[v]]+=siz[mid]-siz[v];
		}
	}
	ans[col[u]]+=without[u];
	return ;
}
inline void clear(int u,int fa) {
	for (auto v : g[u]) {
		if (v==fa) continue;
		clear(v,u);
	}
	g[u].clear(),ans[col[u]]=0,vis[u]=0;
	return ;
}
inline void build() {
	sort(h+1,h+m+1,[](int x,int y){return dfn[x]<dfn[y];});
	vector<int> a;a.clear();
	for (int i=1;i<m;i++) {
		a.push_back(h[i]);
		a.push_back(calc_LCA(h[i],h[i+1]));
	}
	a.push_back(h[m]);
	sort(a.begin(),a.end(),[](int x,int y){return dfn[x]<dfn[y];});
	int sz=unique(a.begin(),a.end())-a.begin();
	rt=a[0];
	for (int i=0;i<sz-1;i++) {
		int LCA=calc_LCA(a[i],a[i+1]);
		if (dfn[rt]>dfn[LCA]) rt=LCA;
		g[LCA].push_back(a[i+1]);
		g[i+1].push_back(a[LCA]);
	}
	return ;
}
inline void solve() {
	cin>>m;
	for (int i=1;i<=m;i++) cin>>h[i],tr[i]=h[i],vis[h[i]]=1;
	build();
	dfs(rt,0);
	df5(rt,rt);dfz(rt,0);
	clear(rt,0);
	for (int i=1;i<=m;i++) cout<<ans[tr[i]]<<" ";
	cout<<endl;
	return ;
}
signed main() {
	cin>>n;
	for (int i=1;i<=n-1;i++) {
		int u,v;cin>>u>>v;
		add(u,v),add(v,u);
	}Top_Tree::build();
	Lowest_Common_Ancestor::build();
	int _;cin>>_;
	while (_--) solve();
	return (0-0);
}
2024/10/19 11:34
加载中...