Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 4141;
- int n;
- vector<int> g[N];
- bool cut_point[N];
- int color[N], hsh[N], cnt[N];
- vector<vector<int>> trees[N];
- int dfs(int u, int p) {
- int ans = 1;
- vector<int> sz;
- for (int v : g[u]) {
- if (v != p) {
- int z = dfs(v, u);
- ans += z;
- sz.push_back(z);
- }
- }
- sz.push_back(n - ans);
- bool ok = true;
- for (int x : sz)
- ok &= (x == sz[0]);
- cut_point[u] = ok && sz.size() > 1;
- return ans;
- }
- void dfs2(int u, int p, int c) {
- color[u] = c;
- for (int v : g[u])
- if (v != p)
- dfs2(v, u, c);
- }
- void dfs3(int u, int p) {
- int c = color[u];
- hsh[u] = cnt[c];
- ++cnt[c];
- for (int v : g[u]) {
- if (v != p) {
- dfs3(v, u);
- trees[c][hsh[u]].push_back(hsh[v]);
- trees[c][hsh[v]].push_back(hsh[u]);
- }
- }
- }
- bool isomorphic(int t1, int t2) {
- // cek if trees[t1].isomorphling(trees[t2]);
- }
- int main() {
- scanf("%d", &n);
- for (int i = 0; i < n - 1; ++i) {
- int u, v;
- scanf("%d %d", &u, &v);
- --u, --v;
- g[u].push_back(v);
- g[v].push_back(u);
- }
- dfs(0, -1);
- int cnt = 0;
- for (int i = 0; i < n; ++i)
- cnt += cut_point[i];
- if (!cnt)
- return 0 * puts("-1");
- assert(cnt == 1);
- int root;
- for (int i = 0; i < n; ++i)
- if (cut_point[i])
- root = i;
- int p = 0;
- for (int v : g[root]) {
- color[v] = ++p;
- dfs2(v, root, p);
- }
- int sz = 0;
- for (int i = 0; i < n; ++i)
- if (color[i] == 1)
- ++sz;
- for (int i = 1; i <= p; ++i)
- trees[i].resize(sz);
- for (int v : g[root])
- dfs3(v, root);
- // bool ok = true;
- // for (int i = 1; i < p; ++i)
- // ok &= isomorphic(i, i + 1);
- // printf("%d\n", (ok ? p : -1));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement