To tackle this problem most effectively, we first establish that the road network described in the problem is a cycle with trees 'coming off' it. So we can root all the trees by the vertex they have on the cycle and denote nodes by 'parent' and children'.
We essentially want to assign an 'id' to the graph surrounding each of the vertices, which is a collection of several subtrees (its children) and a graph that contains the cycle.
There are two ways of doing this, either by computing hash values for each subgraph or by computing 'ids' as we proceed and only hash cyclic shifts of the cycle. The first method is faster in practice and just accurate, but the second is slightly easier to code due to usage of C++ STL.
Since a tree is a collection of its subtrees, we can assign 'id's to all the subtrees rooted at each vertex by proceeding at the outermost layer and proceed inwards.
Then we have to distinguish between all the cyclic shifts (with reflections) of the cycles (which is how we could 'orient' the cycle with respect to the tree the treasure is buried in). This can be accomplished by the standard Rabin-Karp string hash, done once clockwise and once counter clockwise.
Then for each distinct tree, we can just count the trees that have distinct ids by going down recursively, and when we're at a node, only count its children that have distinct ids (so if two of its children have the same subtree, only count one of them). This is correct since the 'root' is now a special node (an orientation of the cycle).
This runs in O(N) time if hashing is used and O(NlogN) if set/map is used. The test data were generated as follows:
Case 1: Sample.
Case 2: 3 chains with different lengths.
Case 3: random tree with edge
Case 4: random tree with edge
Case 5: 10 trees with AAABBCCCBB pattern, N = 53, the trees are specially designed that they cover almost every simple cases.
Case 6: 50 same trees.
Case 7: 20 trees each with 20 nodes.
Case 8: random tree with edge
Case 9: Twin fibonacci trees.
Case 10: A sequence repeated 7 times.
Case 11: A cycle connected with a chain.
Case 12: Repeated ABCACBA pattern.
Case 13: Repeated AB pattern, changed one B into a special big tree.
Case 14: A sequence repeated 6 times with reflection.
Case 15: random tree with edge
Yang Yi's hashing solution:
#include <stdio.h>
#include <string.h>
#define maxn 100000
#define maxh 200003
#define maxH 1000000003LL
int ind[maxn], next[maxn * 2], to[maxn * 2], p;
int n;
int used[maxn];
int f;
int stack[maxn], sp;
int hash[maxh], hashans[maxh], hp;
int hashlib[maxh][3];
long long h1[maxn], h2[maxn];
long long hash2[maxh];
int addhash (int *data) {
long long c = 123456;
for (int i = 0; i < 3; i ++)
c = c * 47 ^ data[i];
c = c * 47 % maxh;
while (hash[c] != -1 && (hashlib[c][0] != data[0] || hashlib[c][1] !=
data[1] || hashlib[c][2] != data[2])) {
c ++;
if (c == maxh)
c = 0;
}
if (hash[c] == -1) {
hashlib[c][0] = data[0];
hashlib[c][1] = data[1];
hashlib[c][2] = data[2];
hash[c] = hp ++;
}
return hash[c];
}
int add2 (long long x, int i) {
long long c = x % maxh;
c = c * 47 % maxh;
while (hash2[c] != -1 && hash2[c] != x) {
c ++;
if (c == maxh)
c = 0;
}
if (hash2[c] == -1) {
hash2[c] = x;
hash[c] = i;
return -1;
}
else
return hash[c];
}
int test (int a, int b) {
for (int i = 0; i < sp; i ++)
if (stack[i + a >= sp? i + a - sp: i + a] != stack[i + b >= sp? i
+ b -
sp: i + b])
return 0;
return 1;
}
int dfs2 (int x, int dad) {
int lib[3], lp = 0;
for (int i = ind[x]; i != -1; i = next[i])
if (to[i] != dad && !used[to[i]])
lib[lp ++] = dfs2(to[i], x);
if (dad == -1)
lib[lp ++] = maxh - 2;
while (lp < 3)
lib[lp ++] = maxh - 1;
for (int i = 0; i < 3; i ++)
for (int j = 0; j < 2; j ++)
if (lib[j] > lib[j + 1])
lib[j] ^= lib[j + 1] ^= lib[j] ^= lib[j + 1];
lp = addhash(lib);
int ans = 0;
for (int i = 0; i < 3; i ++)
if (lib[i] != maxh - 1 && lib[i] != maxh - 2 && (i == 0
|| lib[i] !=
lib[i-1]))
ans += hashans[lib[i]];
if (lib[2] == maxh - 1)
ans ++;
hashans[lp] = ans;
return lp;
}
void dfs (int x, int dad) {
if (f)
return;
if (used[x] != 0xFEFEFEFE) {
f = 1;
sp = 0;
dad = to[dad];
stack[sp ++] = dad;
while (dad != x) {
dad = used[dad];
stack[sp ++] = dad;
}
return;
}
used[x] = dad == -1? -1 : to[dad];
for (int i = ind[x]; i != -1; i = next[i])
if (i != dad)
dfs(to[i], i^1);
}
int main () {
int i, a, b, c;
freopen("cowmstr.in", "r", stdin);
freopen("cowmstr.out", "w", stdout);
scanf("%d",&n);
p = 0;
memset(ind, -1, sizeof(ind));
for (i = 0; i < n; i ++) {
scanf("%d%d",&a,&b);
a --;
b --;
next[p] = ind[a];
to[p] = b;
ind[a] = p ++;
next[p] = ind[b];
to[p] = a;
ind[b] = p ++;
}
memset(used, -2, sizeof(used));
f = 0;
sp = 0;
dfs(0, -1);
memset(used, 0, sizeof(used));
for (i = 0; i < sp; i ++)
used[stack[i]] = 1;
/*
for (i = 0; i < sp; i ++)
printf("%d\n",stack[i]);
fflush(stdout);
*/
memset(hash, -1, sizeof(hash));
hp = 0;
for (i = 0; i < sp; i ++)
stack[i] = dfs2(stack[i], -1);
long long big = 1;
h1[0] = 0;
for (i = sp - 1; i >= 0; i --) {
h1[0] = (h1[0] * 147804523 + stack[i]) % maxH;
big = big * 147804523 % maxH;
}
for (i = sp - 1; i > 0; i --)
h1[i] = (h1[(i + 1) % sp] * 147804523 % maxH + stack[i] + maxH - big *
stack[i] % maxH) % maxH;
h2[0] = 0;
for (i = 1; i < sp; i ++)
h2[0] = (h2[0] * 147804523 + stack[i]) % maxH;
h2[0] = (h2[0] * 147804523 + stack[0]) % maxH;
for (i = 1; i < sp; i ++)
h2[i] = (h2[i - 1] * 147804523 % maxH + stack[i] + maxH - big *
stack[i] % maxH) % maxH;
memset(hash2, -1, sizeof(hash2));
a = -1;
for (i = 0; a == -1 && i < sp; i ++)
if ((b = add2(h1[i], i)) != -1)
if (test(b, i))
a = i - b;
if (a == -1)
a = sp;
b = 0;
c = 0;
for (i = 0; i < sp; i ++) {
if (h1[i] == h2[i]) {
b |= 1;
c = i;
}
if (h1[i] == h2[(i + 1) % sp] && !(b&1)) {
b |= 2;
c = (i + 1) % sp;
}
}
if (b & 1)
a = a / 2 + 1;
else
if (b & 2)
a = a / 2;
int ans = 0;
for (i = 0; i < a; i ++)
ans += hashans[stack[(i + c) % sp]];
printf("%d\n", ans);
return 0;
}