80pts 求助
查看原帖
80pts 求助
416242
New_hope楼主2024/7/14 20:30
#include <bits/stdc++.h>
#define _ 200
typedef unsigned long long ull;
using namespace std;

const ull P = 998244353;
struct pr
{
	ull k1, k2;
	bool operator == (const pr &a)const {
		return k1 == a.k1 && k2 == a.k2;
	}
} key[_];
int m, w, mn;
int siz[_], wei[_], ans[_], cent[2];
bool print[_];
vector <int> t[_];

ull f(ull x)
{
	x ^= P, x ^= x << 13, x ^= x >> 7, x ^= x << 17, x ^= P;
	return x;
}
bool cmp(pr a, pr b) 
{
	if (a.k1 != b.k1) {
		return a.k1 < b.k1;
	} else if (a.k2 != b.k2) {
		return a.k2 < b.k2;
	}
}
void init()
{
	for (int i(0); i < _; i ++) {
		t[i].clear();
		siz[i] = wei[i] = 0;	
	} cent[0] = cent[1] = 0;
	mn = 2e9;
}
void dfs(int u, int p, int n)
{
	siz[u] = 1;
	for (int v : t[u]) {
		if (v == p) continue;
		dfs (v, u, n); siz[u] += siz[v];
		wei[u] = max(wei[u], siz[v]);
	} wei[u] = max(wei[u], n - siz[u]);
	if (wei[u] <= mn) {
		cent[0] = u;  
		mn = wei[u];
	} 
}
ull hsh(int u, int p)
{
	ull add(0), w;
	for (int v : t[u]) {
		if (v == p) continue;
		add += hsh(v, u);
	}
	return w = f(1 + add);
}

int main()
{
	scanf ("%d", &m);
	for (int i(1); i <= m; i ++) {
		int nd, rt; scanf ("%d", &nd);
		init(); 
		for (int j(1); j <= nd; j ++) {
			int fa; scanf ("%d", &fa);
			if (!fa) {
				rt = j;
				continue;	
			}
			t[fa].push_back(j);
			t[j].push_back(fa);
		}
		dfs(rt, 0, nd); 
		for (int j(1); j <= nd; j ++) {
			if (mn == wei[j] && j != cent[0]) {
				cent[1] = j; break;
			}  
		}
		key[i].k1 = hsh(cent[0], 0);
		if (!cent[1]) {
			key[i].k2 = key[i].k1;
		} else {
			key[i].k2 = hsh(cent[1], 0);
		}
		key[i].k1 = max(key[i].k1, key[i].k2);
		key[i].k2 = min(key[i].k1, key[i].k2);
	}
	for (int i(1); i <= m; i ++) {
		if (!print[i]) {
			print[i] = 1;
			ans[i] = i;
		}
		for (int j(i + 1); j <= m; j ++) {
			if (key[i].k1 == key[j].k1 && key[i].k2 == key[j].k2 && !print[j]) {
				ans[j] = i, print[j] = 1;
			}
		}
	} 
	for (int i(1); i <= m; i ++) {
		printf ("%d\n", ans[i]);
	}
	
	return 0;
}
2024/7/14 20:30
加载中...