MENU

BZOJ4337 BJOI2015 树的同构

BZOJ4337

树hash模板。

有根树hash可以转成括号序列,无根树找到重心转为有根树。按照字典序排序以保证唯一。

#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
struct io {
    static const int L = (1 << 21) + 1;
    char ibuf[L], *iS, *iT, obuf[L], *oS, *oT, st[50];
    void flush() { fwrite(obuf, 1, oS - obuf, stdout), oS = obuf; }
    void putc(char X) {
        *oS++ = X;
        if(oS == oT)flush();
    }
    char gc() { return iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin), (iS == iT ? EOF : *iS++)) : *iS++; }
    template<class T>T rd() {
        int c = gc();
        T X = 0;
        for(; !isdigit(c); c = gc());
        for(; isdigit(c); c = gc())X = X * 10 + (c & 15);
        return X;
    }
    template<class T>void print(T X) {
        if(!X) { putc('0'); return; }
        int tp = 0;
        for(; X; st[tp++] = X % 10 + 48, X /= 10);
        for(tp--; ~tp; putc(st[tp--]));
    }
    io() :oS(obuf), oT(obuf + L - 1) {}
    ~io() { fwrite(obuf, 1, oS - obuf, stdout); }
}ip;
int M = ip.rd<int>(), N, head[51], cnt, sz[51], mn, f[51];
struct edge {
    int v, next;
    edge(int v = 0, int next = 0) :v(v), next(next) {}
}e[101];
inline void add(int u, int v) { e[++cnt] = edge(v, head[u]), head[u] = cnt, e[++cnt] = edge(u, head[v]), head[v] = cnt; }
inline void dfs1(int u, int fa) {
    int cur = 0;
    sz[u] = 1;
    for(int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == fa)continue;
        dfs1(v, u);
        sz[u] += sz[v];
        cur = max(cur, sz[v]);
    }
    cur = max(cur, N - sz[u]);
    mn = min(mn, f[u] = cur);
}
string a[51], temp[51], val[51];
inline void dfs2(int u, int fa) {
    a[u] = "(";
    for(int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == fa)continue;
        dfs2(v, u);
    }
    int cnt = 0;
    for(int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == fa)continue;
        temp[cnt++] = a[v];
    }
    if(cnt > 1)std::sort(temp, temp + cnt);
    for(int i = 0; i < cnt; ++i)a[u] += temp[i];
    a[u] += ")";
}
inline string gao() {
    N = ip.rd<int>(), cnt = 0;
    for(int i = 1; i <= N; ++i)head[i] = 0;
    int x;
    for(int i = 1; i <= N; ++i)if(x = ip.rd<int>())add(i, x);
    mn = 51, dfs1(1, 0);
    string ret;
    for(int i = 1; i <= N; ++i)if(f[i] == mn)dfs2(i, 0), ret = max(ret, a[i]);
    return ret;
}
int main() {
    for(int i = 1; i <= M; ++i) {
        val[i] = gao();
        int j = 1;
        for(; j < i; ++j)if(val[i] == val[j])break;
        ip.print(j), ip.putc('\n');
    }
}
Leave a Comment

captcha
请输入验证码