题解

因为博主退役了，所以题解咕掉了。先放个代码

CODE

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2005;

int n, ps[MAXN], ans[MAXN], fir[MAXN], to[MAXN<<1], nxt[MAXN<<1], cntE, Mn;

int f[MAXN][MAXN<<1], cnt[MAXN]; bool bf[MAXN<<1], st[MAXN], ed[MAXN];

inline void link(int u, int v) {

	to[++cntE] = v; nxt[cntE] = fir[u]; fir[u] = cntE;

	to[++cntE] = u; nxt[cntE] = fir[v]; fir[v] = cntE;

}

int find(int u, int x) { return !f[u][x] ? x : f[u][x] = find(u, f[u][x]); }

void dfs(int u, int ff) {

	if(ff && !f[u][ff] && !ed[u] && (find(u, 2*n+2) != ff || cnt[u] == 1)) Mn = min(Mn, u);

	for(int i = fir[u]; i; i = nxt[i]) if(i^ff)

		if( (!ff && !st[u] && !bf[i] && (find(u, i) != 2*n+3 || cnt[u] == 1))

		|| (ff && !f[u][ff] && !bf[i] && find(u, i) != ff && (find(u, 2*n+2) != ff || find(u, i) != 2*n+3 || cnt[u] == 2)))

			dfs(to[i], i^1);

}

bool mdf(int u, int ff) {

	if(u == Mn) { f[u][ff] = 2*n+3, ed[u] = 1; return 1; }

	for(int i = fir[u]; i; i = nxt[i]) if((i^ff) && mdf(to[i], i^1)) {

		if(!ff) f[u][2*n+2] = i, st[u] = 1, bf[i] = 1;

		else f[u][ff] = i, --cnt[u], bf[i] = 1;

		return 1;

	}

	return 0;

}

int main(){

	freopen("tree.in","r",stdin);

	freopen("tree.out","w",stdout);

	int T; scanf("%d", &T);

	while(T--) {

		memset(f, 0, sizeof f);

		memset(bf, 0, sizeof bf);

		memset(st, 0, sizeof st);

		memset(ed, 0, sizeof ed);

		memset(fir, 0, sizeof fir);

		memset(cnt, 0, sizeof cnt);

		cntE = 1;

		scanf("%d",&n);

		for(int i = 1; i <= n; ++i)	scanf("%d", &ps[i]);

		for(int i = 1, x, y; i < n; ++i) scanf("%d%d", &x, &y), ++cnt[x], ++cnt[y], link(x, y);

		for(int i = 1; i <= n; ++i) Mn = n, dfs(ps[i], 0), mdf(ps[i], 0), ans[i] = Mn;

		for(int i = 1; i <= n; ++i) printf("%d%c", ans[i], " \n"[i==n]);

	}

}

巴特西

CSP2019 D1T3 树上的数（贪心+并查集）

题解

CODE

最新文章

热门文章

巴特西

CSP2019 D1T3 树上的数 （贪心+并查集）

题解

CODE

最新文章

热门文章

CSP2019 D1T3 树上的数（贪心+并查集）