这个似乎就是对的了- -..

#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 2000100
using namespace std;
#define pushvc(_v,_t) _v.push_back(_t)
#define hashmod 998244353
namespace graph{
    struct node;
    struct edge{
        node* t;
        edge* n;
        edge(node* t=NULL,edge* n=NULL):t(t),n(n){}
    };
    struct node{
        int id;
        edge* h;
        node(int id=0,edge* h=NULL):id(id),h(h){}
    };
    struct graph{ // utility for storing a graph, and later convert to a tree
        node nodes[maxn];
        edge edges[maxn<<1];
        int edgeSize,nodeCount;
        graph(int edgeSize=0,int nodeCount=0):edgeSize(edgeSize),nodeCount(nodeCount){}
        inline void addedge(node* a,node* b){
            ++edgeSize;
            edges[edgeSize]=(edge){b,a->h};
            a->h=edges+edgeSize;
        }
        inline void bidedge(node* a,node* b){
            addedge(a,b); addedge(b,a);
        }
        inline node* newNode(){
            ++nodeCount;
            nodes[nodeCount].id=nodeCount;
            return nodes+nodeCount;
        }
        inline node& operator[](int n){
            return nodes[n];
        }
        inline node* operator+ (int n){
            return nodes+n;
        }
    };
    struct unrooted_tree{
        struct node_data{
            int tot_sub,max_sub;
        } nt_nds[maxn];
        graph grf;
        int size;
        node* wc[10];
        int sizewc;
        int mimasubtree;
        unrooted_tree(int _size=0){
            size=_size;
            if(_size){
                while(_size){
                    grf.newNode();
                    --_size;
                }
            }
        }
        inline int _gwc_dfs(node* n,node* f){
            nt_nds[n->id].max_sub=0;
            nt_nds[n->id].tot_sub=1;
            for(edge* i=n->h;i;i=i->n){
                if(i->t == f) continue;
                int q=_gwc_dfs(i->t,n);
                nt_nds[n->id].tot_sub+=q;
                if(q > nt_nds[n->id].max_sub) nt_nds[n->id].max_sub=q;
            }
            if((size-nt_nds[n->id].tot_sub) > nt_nds[n->id].max_sub)
                nt_nds[n->id].max_sub=size-nt_nds[n->id].tot_sub;
            return nt_nds[n->id].tot_sub;
        }
        inline void pushwc(node* p){
            wc[++sizewc]=p;
        }
        inline int getwcs(){ // get weight centers, return the number of weight centers.
            _gwc_dfs(grf+1,NULL);
            mimasubtree=0x7fffffff;
            sizewc=0;
            for(int i=1;i<=size;++i) if(nt_nds[i].max_sub < mimasubtree) mimasubtree=nt_nds[i].max_sub;
            for(int i=1;i<=size;++i) if(nt_nds[i].max_sub== mimasubtree) pushwc(grf+i);
            return sizewc;
        }
        FILE* otd; // for dot file output
        inline void _print_dfs(node* n,node* f){
            fprintf(otd,"A%d[label=\"#%d\"];\n",n->id,n->id);
            for(edge* i=n->h;i;i=i->n){
                if(i->t == f) continue;
                fprintf(otd,"A%d -> A%d;\n",n->id,i->t->id);
                _print_dfs(i->t,n);
            }
        }
        inline void print_dot(node* asroot){
            fprintf(otd,"digraph{\n"
                    "    node[color=\"#2266ff\",fillcolor=\"#aaccff\",fontname=\"Courier\",regular=true];\n");
            _print_dfs(asroot,NULL);
            fprintf(otd,"}\n");
        }
        inline void openOutputFile(const char* filename){
            if(otd) fclose(otd),otd=NULL;
            otd=fopen(filename,"w");
        }
    };
//    FILE* otd; // for dot file output
//    inline void mopenOutputFile(const char* filename){
//        if(otd) fclose(otd),otd=NULL;
//        otd=fopen(filename,"w");
//    }
    struct rooted_tree{
        int size,maxdepth,hash;
        node* root;
        vector<rooted_tree*> sons;
        void build(node* p,node* f);
        void print();
    };
    inline int cmp_same (rooted_tree* a,rooted_tree* b){
        if(a->size - b->size) return a->size - b->size;
        if(a->maxdepth - b->maxdepth) return a->maxdepth - b->maxdepth;
        if(a->hash - b->hash) return a->hash - b->hash;
        int ax=a->sons.size(),bx=b->sons.size();
        if(ax - bx) return ax - bx;
        for(int i=0;i<ax;++i){
            int q=cmp_same(a->sons[i],b->sons[i]);
            if(q) return q;
        }
        return 0;
    }
    inline bool cmp_build(const rooted_tree* a,const rooted_tree* b){
        if(a->size - b->size) return a->size > b->size;
        if(a->maxdepth - b->maxdepth) return a->maxdepth > b->maxdepth;
        if(a->hash - b->hash) return a->hash > b->hash;
        int ax=a->sons.size(),bx=b->sons.size();
        if(ax - bx) return ax > bx;
        for(int i=0;i<ax;++i){
            int q=cmp_same(a->sons[i],b->sons[i]);
            if(q) return q>0;
        }
        return 0;
    }
    void rooted_tree::build(node* p,node* f){
        root=p; size=1; maxdepth=0; hash=1;
        for(edge* i=p->h;i;i=i->n){
            if(i->t == f) continue;
            rooted_tree* s1=new rooted_tree;
            s1->build(i->t,p);
            pushvc(sons,s1);
            size+=s1->size;
            if(s1->maxdepth > maxdepth) maxdepth=s1->maxdepth;
        }
        ++maxdepth;
        sort(sons.begin(),sons.end(),cmp_build);
        for(int i=0,_=sons.size();i<_;++i){
            hash=((long long)hash+(long long)sons[i]->hash*(long long)(i+1))%hashmod;
            //some very weak hash function, because the time complexity is
            //provided O(nlogn) total, so it is just a speed up
        }
    }
    bool isiso(unrooted_tree* a,unrooted_tree* b){
        if(a->size != b->size) return 0;
        a->getwcs();
        int q=b->getwcs();
        if(a->sizewc != b->sizewc) return 0;
        if(a->mimasubtree != b->mimasubtree) return 0;
        rooted_tree* ptree=new rooted_tree;
        ptree->build(a->wc[1],NULL); // build an minimized tree
        for(int i=1;i<=q;++i){
            rooted_tree* qtree=new rooted_tree;
            qtree->build(b->wc[i],NULL);
            if(!cmp_same(ptree,qtree)) return 1;
        }
        return 0;
    }
    inline unrooted_tree* readTree_byEdge(){
        int n;
        scanf("%d",&n);
        unrooted_tree* p=new unrooted_tree(n);
        for(int i=1,a,b;i<n;++i){
            scanf("%d%d",&a,&b);
            p->grf.bidedge(p->grf+a,p->grf+b);
        }
        return p;
    }
    void rooted_tree::print(){
        printf("Access node %d with %d sons,Fields: size %d maxdepth %d hash%d\n",
            root->id,sons.size(),size,maxdepth,hash);
        if(sons.size()){
            printf("Sons:");
            for(int i=0;i<sons.size();++i) printf("%d ",sons[i]->root->id);
            putchar('\n');
            for(int i=0;i<sons.size();++i) sons[i]->print();
        }
    }
}
using namespace graph;
int main(){
    unrooted_tree* p=readTree_byEdge();
    unrooted_tree* q=readTree_byEdge();
//    p->openOutputFile("out.dot");
//    p->getwcs();
//    p->print_dot(p->wc[1]);
//    printf("%d %d %d\n",p->wc[1]->id,p->mimasubtree,p->wc[2]->id);
//    rooted_tree* k=new rooted_tree;
//    k->build(p->wc[1],NULL);
//    k->print();
//    rooted_tree* kq=new rooted_tree;
//    if(p->wc[2]){
//        kq->build(p->wc[2],NULL);
//        kq->print();
//        printf("%s\n",cmp_same(k,kq)?"Diff":"Same");
//    }
    printf("%s\n",isiso(p,q)?"Same":"Diff");
    return 0;
}

似乎跑得很慢?当然可以跑得更快的...