CF E2 求调,Dsu on Tree
  • 板块学术版
  • 楼主Loser_Syx
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/1/27 01:06
  • 上次更新2025/1/27 14:19:01
查看原帖
CF E2 求调,Dsu on Tree
852144
Loser_Syx楼主2025/1/27 01:06
#include <iostream>
#include <cassert>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <random>
#include <chrono>
#include <ctime>
#include <map>
#include <set>
using namespace std;
#define int long long
#define pii pair<int, int>
#define eb emplace_back
#define F first
#define S second
#define test(x) cout << "Test: " << (x) << '\n'
#define lowbit(x) (x & -x)
#define debug puts("qwq");
#define open(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define close fclose(stdin);fclose(stdout);
namespace FastIO {
	template <typename T = int>
	inline T read() {
		T s = 0, w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		return s * w;
	}
	template <typename T>
	inline void read(T &s) {
		s = 0;
		int w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		s = s * w;
	}
	template <typename T, typename... Arp> inline void read(T &x, Arp &...arp) {
		read(x), read(arp...);
	}
	template <typename T>
	inline void write(T x, char ch = '\n') {
		if (x < 0) x = -x, putchar('-');
		static char stk[25];
		int top = 0;
		do {
			stk[top++] = x % 10 + '0', x /= 10;
		} while (x);
		while (top) putchar(stk[--top]);
		putchar(ch);
		return;
	}
	template <typename T>
	inline void smax(T &x, T y) {
		if (x < y) x = y;
	}
	template <typename T>
	inline void smin(T &x, T y) {
		if (x > y) x = y;
	}
	void quit() {
		exit(0);
	}
} using namespace FastIO;
const int N = 4e5 + 19;
int n, w[N], siz[N], cnt, dfn[N], now[N], son[N]; vector<int> g[N], mp[N];
void dfs(int u, int fa) {
	siz[u]=1; dfn[u]=++cnt; now[cnt]=u;
	for (int v:g[u]) if (v^fa) {
		dfs(v,u); siz[u]+=siz[v];
		if (siz[v]>siz[son[u]]) son[u]=v;
	}
}
struct SegTree {
	int t[N << 2], cnt[N << 2];
	#define ls (k << 1)
	#define rs (k << 1 | 1)
	#define mid ((l + r) >> 1)
	void modify(int k, int l, int r, int s, int w) {
		if (l == r) {
			if (w == 1 && t[k] == 0) ++cnt[k];
			if (w == -1 && t[k] == 1) --cnt[k];
			t[k] += w;
			return ;
		}
		if (s <= mid) modify(ls, l, mid, s, w);
		else modify(rs, mid+1, r, s, w);
		cnt[k] = cnt[ls] + cnt[rs];
	}
	int query(int k, int l, int r, int L, int R) {
		if (L <= l && r <= R) return cnt[k];
		int ans = 0;
		if (L <= mid) ans += query(ls, l, mid, L, R);
		if (R > mid) ans += query(rs, mid+1, r, L, R);
		return ans;
	}
} t;
vector<int> ans;
int tot=0, o[N];
void solve(int u, int fa, int p = 0) {
	for (int v:g[u]) if (v^fa&&v^son[u]) solve(v,u);
	if (son[u]) solve(son[u],u,1); t.modify(1,1,n,w[u],-1);
	for (int v:g[u]) if (v^fa&&v^son[u]) {
		for (int i=dfn[v];i<=dfn[v]+siz[v]-1;++i) t.modify(1,1,n,w[now[i]],-1);
	} if (w[u]!=n&&t.query(1,1,n,w[u]+1,n) == 1) ans.eb(u);
	if (!p) {
		for (int i = dfn[u]; i <= dfn[u] + siz[u] - 1; ++i) t.modify(1,1,n,w[now[i]], 1);
	}
}
void clear() {
	for (int i=1;i<=n;++i) {
		g[i].clear(); mp[i].clear();
		t.modify(1,1,n,w[i],-1); cnt=0; son[i]=siz[i]=dfn[i]=now[i]=0;
	} ans.clear();
}
void solve() {
	read(n); 
	for (int i=1;i<=n;++i) read(w[i]);
	for (int i=1,u,v;i<n;++i) {
		read(u,v); g[u].eb(v); g[v].eb(u);
	} for (int i=1;i<=n;++i) t.modify(1,1,n,w[i],1);
	dfs(1,0); solve(1, 0);
	sort(ans.begin(),ans.end());
	write(ans.size(),' '); for (int v:ans) write(v, ' ');
	puts("");
	clear();
	return ;
}
signed main() {
	int t = read();
	while (t--) solve();
	return 0;
}
2025/1/27 01:06
加载中...