一晚上写了一道傻逼题，这不是日常吗。
de到死亡，怀疑人生，然后重构
//Achen#include#include #include #include #include #include #include #include #include const int N=55;const int mod=1e9+7;const int base=131;typedef long long LL;using namespace std;int n,m,top;LL hs[N][N],has[N],tp[N],que[N];template void read(T &x) { T f=1; x=0; char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') f=-1,ch=getchar(); for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;}int ecnt,fir[N],nxt[N<<1],to[N<<1];void add(int u,int v) { nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u;}void dfs(int x,int fa) { for(int i=fir[x];i;i=nxt[i]) if(to[i]!=fa) dfs(to[i],x); tp[x]=0; top=0; for(int i=fir[x];i;i=nxt[i]) if(to[i]!=fa) que[++top]=tp[to[i]]; if(!top) {tp[x]=233; return;} sort(que+1,que+top+1); for(int i=1;i<=top;i++) tp[x]=(tp[x]^que[i])*base%mod;}int main() { read(m); for(int i=1;i<=m;i++) { read(n); memset(fir,0,sizeof(fir)); ecnt=0; for(int j=1;j<=n;j++) { int fa; read(fa); if(fa) add(fa,j); } for(int j=1;j<=n;j++) { dfs(j,0); hs[i][j]=tp[j]; } sort(hs[i]+1,hs[i]+n+1); for(int j=1;j<=n;j++) has[i]=(has[i]^hs[i][j])*233%mod; for(int j=1;j<=i;j++) if(has[i]==has[j]) { printf("%d\n",j); break; } } return 0;}
至今不懂注释为何WA
//Achen#include#include #include #include #include #include #include #include #include const int N=55;typedef long long LL;using namespace std;int n,m;LL hs[N][N],has[N],base,mod,node[N],tp[N]; template void read(T &x) { T f=1; x=0; char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') f=-1,ch=getchar(); for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;}int ecnt,fir[N],nxt[N<<1],to[N<<1]; void add(int u,int v) { nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u;}int que[N],top; void dfs(int x,int fa) { for(int i=fir[x];i;i=nxt[i]) if(to[i]!=fa) dfs(to[i],x); tp[x]=0; top=0; for(int i=fir[x];i;i=nxt[i]) if(to[i]!=fa) que[++top]=tp[to[i]]; if(!top) {tp[x]=233; return;} sort(que+1,que+top+1); for(int i=1;i<=top;i++) tp[x]=(tp[x]^que[i])*base%mod;}int main() { read(m); base=131; mod=1e9+7; for(int i=1;i<=m;i++) { read(n); memset(fir,0,sizeof(fir)); ecnt=0; for(int j=1;j<=n;j++) { int fa; read(fa); if(fa) add(fa,j); } for(int j=1;j<=n;j++) { dfs(j,0); hs[i][j]=tp[j]; } sort(hs[i]+1,hs[i]+n+1); for(int j=1;j<=n;j++) has[i]=(has[i]^hs[i][j])*233%mod; for(int j=1;j<=i;j++) if(has[i]==has[j]) { printf("%d\n",j); break; } } /*for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(has[i]==has[j]) { printf("%d\n",j); break; }*/ return 0;}