蒟蒻求助树哈希WA on #5
查看原帖
蒟蒻求助树哈希WA on #5
271375
ywli08楼主2023/9/30 16:49
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
const ll inf = 1e9+7;
const ll mod = 1e9+7;
 
struct edge{
	int from, to;
	int wt;
	int nxt, id;
}G[maxn << 1];
int head[maxn], cnt;
void add(int u, int v, int w, int id){
	G[++cnt] = {u, v, w, head[u], id};
	head[u] = cnt;
}
 
bool k[maxn << 1];
ll p[maxn << 1], t;
void isprime(ll n){
	k[1] = 1;
	for(int i = 2;i <= n;i++){
		if(!k[i]) p[++t] = i;
		for(int j = 1;j <= t && i * p[j] <= n;j++){
			k[p[j] * i] = 1;
			if(i % p[j] == 0) break;
		}
	}
	return ;
}
 
ll n, m;
ll a[maxn];
ll hsh[maxn], hshx[maxn], size[maxn], out[maxn];
ll ans[maxn], id;
map<ll, ll> st;
 
void dfs(int u, int f){
	hsh[u] = 1; size[u] = 1;
	for(int i = head[u];i;i = G[i].nxt){
		int v = G[i].to;
		if(v == f) continue;
		dfs(v, u);
		hsh[u] = (hsh[u] + p[size[v]] * hsh[v] % mod) % mod;
		size[u] += size[v];
	}
}
 
inline void ins(ll x){
	if(st.count(x) == 0) st[x] = 1;
	else st[x] += 1;
}
 
inline void del(ll x){
	st[x] -= 1;
	if(st[x] <= 0) st.erase(x);
}
 
inline void print(){
	for(auto i:st){
		cout << i.first << ' ' << i.second << endl;
	}
	cout << "----------------------" << endl;
}
 
void dfs2(int u, int f){
	if(u != 1){
		out[f] = ((hshx[f] - hsh[u] * p[size[u]]) % mod + mod) % mod;
		hshx[u] = (hsh[u] + out[f] * p[size[1] - size[u]] % mod) % mod;
		del(hshx[f]);
		ins(out[f]);
		del(hsh[u]);
		ins(hshx[u]);
	}
//	print();
	for(int i = head[u];i;i = G[i].nxt){
		int v = G[i].to;
		if(v == f) continue;
		dfs2(v, u);
	}
//	print();
	ans[u] = st.size();
	if(ans[u] >= ans[id]){
		id = u;
	}
	if(u != 1){
		ins(hshx[f]);
		del(out[f]);
		ins(hsh[u]);
		del(hshx[u]);
	}
//	print();
	return ;
}
 
int main(){
	cin >> n;
	for(int i = 1;i < n;i++){
		ll x, y;
		cin >> x >> y;
		add(x, y, 1, i);
		add(y, x, 1, i);
	}
	isprime(2e5);
	dfs(1, 0);
	out[1] = hshx[1] = hsh[1];
	for(int i = 1;i <= n;i++){
		st[hsh[i]] = 1;
	}
	dfs2(1, 0);
//	cout << ans[id] << endl;
	cout << id << endl;
}

dalao们救救孩子吧,卡了几天了。。。

2023/9/30 16:49
加载中...