Gold_7's Blog

跪了跪了。。没事反正跪习惯了

呃是jsoi2015 day1

T1

f[i]表示以i为根的子树的答案。

u[i]表示以i为根的子树的答案是否unique。

嗯。。f贪心一下就可以了。

u:设贪心了k个儿子

• 如果取的k个中有答案不唯一的，则答案不唯一
• 如果前k个中有0,则答案不唯一(啊我错了)
• 如果第k个和第k+1个相同，则答案不唯一（当然儿子数要>=k+1）

T2

//听说是道不难死你也要烦死你的题。。窝太懒先留个坑

矩阵hash咯

T3

去掉假节点很简单，然后就是无根树同构。

于是只要选几个东西hash一下，正确性要求不高，毕竟只有20棵树。。

然而我选了度数，自然被卡飞（30分不错耶）。。可以拓扑每层节点数，能A

然后是正解

窝萌只会有根树同构是不是，那么有许多解决方案

• 求树的重心，如果有两个，这两个中间加个点作为重心
• 拓扑到只剩1个或2个点。2个点分别做，再hash起来

这方法极不推荐（小心码长被人碾）

于是lh一语道破（太精妙了我膜拜不已）

无向图同构：给每个点一个初始hash值1。每轮中，对于每个点，取出其邻点的hash值，sort之后hash起来，作为这个点的新hash值。若干轮（实际是2轮？数据水了吧）之后，将所有点的值再sort，hash，代表这个图。

然后就没有了。。

嗯。。zj18au,js5au,js第五170。。

%NiroBC190

#include<bits/stdc++.h>
using namespace std;
#define SC scanf
#define U_(i,a,b) for(int i=a;i<=b;i++)
#define D_(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll;
#define MK make_pair
#define A first
#define B second
const int N=200000;
struct EG{int a,b;}eg[N<<1];
int head[N],en;
int ans[N];
int b[N],n;
bool uni[N];
void add(int u,int v){
    eg[++en]=(EG){v,head[u]};
    head[u]=en;
}
void dfs(int u,int fa){
    priority_queue<pair<int,int> >q;
    int son=0;
    bool flg=0;
    for(int e=head[u];e;e=eg[e].b){
        int v=eg[e].a;
        if(v==fa)continue;
        dfs(v,u);
        q.push(MK(ans[v],v));
        if(ans[v]==0)flg=1;
        son++;
    }
    int tmp;
    U_(i,1,min(son,b[u]-1)){
        if(q.top().A<0)break;
        if(q.top().A==0){flg=1;break;}
        tmp=q.top().A;
        flg|=uni[q.top().B];
        {ans[u]+=q.top().A;q.pop();}
    }
    if(!q.empty()&&tmp==q.top().A)flg=1;
    uni[u]=flg;
}
int main(){//freopen("salesman.in","r",stdin);freopen("salesman.out","w",stdout);
    SC("%d",&n);
    ans[1]=0;b[1]=1000000000;
    U_(i,2,n)SC("%d",&ans[i]);
    U_(i,2,n)SC("%d",&b[i]);
    U_(i,1,n-1){
        int u,v;
        SC("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs(1,1);
    printf("%d\n",ans[1]);
    if(!uni[1])puts("solution is unique");else puts("solution is not unique");
}

#include<bits/stdc++.h>
using namespace std;
#define SC scanf
#define U_(i,a,b) for(int i=a;i<=b;i++)
#define D_(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll;
#define MK make_pair
#define A first
#define B second
#define CK(x) check_##x
#define CHK(x,len,i,j) check_##x(len,i,j)
typedef unsigned int uint;
typedef unsigned long long ull;
const int N=511,d1=233,d2=2333;
uint h[N][N],h0[N][N],h1[N][N],h2[N][N],h3[N][N],h4[N][N],h5[N][N],pow1[N],pow2[N];
int n;
void init(){
    SC("%d",&n);
    static char s[N];
    U_(i,1,n){
        SC("%s",s+1);
        U_(j,1,n)h[i][j]=s[j]-'0';
    }
    pow1[0]=1;U_(i,1,n)pow1[i]=pow1[i-1]*d1;
    pow2[0]=1;U_(i,1,n)pow2[i]=pow2[i-1]*d2;
}
void build(){
    U_(i,1,n)U_(j,1,n)if(h[i][j])
        h0[i][n-j+1]=h1[n-i+1][j]=h2[j][i]=h3[n-j+1][n-i+1]=h4[j][n-i+1]=h5[n-i+1][n-j+1]=1;
}
void get(uint a[][N]){
    U_(i,1,n){
        int p=pow1[n-i];
        U_(j,1,n)a[i][j]=a[i][j]*p*pow2[n-j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
    }
}
void gethash(){get(h),get(h0),get(h1),get(h2),get(h3),get(h4),get(h5);}
uint gao(uint h[][N],int len,int x,int y){return (h[x][y]-h[x-len][y]-h[x][y-len]+h[x-len][y-len])*pow1[x]*pow2[y];}
bool check_0(const int len,const int x,const int y){
    uint tmp=gao(h,len,x,y);
    return tmp==gao(h0,len,x,n-y+len)||tmp==gao(h1,len,n-x+len,y)||tmp==gao(h2,len,y,x)||tmp==gao(h3,len,n-y+len,n-x+len);
}
bool check_90(int &len,int &x,int &y){return gao(h,len,x,y)==gao(h4,len,y,n-x+len);}
bool check_180(int &len,int &x,int &y){return gao(h,len,x,y)==gao(h5,len,n-x+len,n-y+len);}
bool check_4(int &len,int &x,int &y){return CHK(180,len,x,y)&&CHK(0,len,x,y);}
bool check_8(int &len,int &x,int &y){return CHK(90,len,x,y)&&CHK(0,len,x,y);}
template<class T>bool check(int len,T f){
    U_(i,len,n)U_(j,len,n)if(f(len,i,j))return 1;
    return 0;
}
template<class T>int calc(T f){
    int l=1,r=n/2,mid;
    while(l<=r){
        mid=l+r>>1;
        if(check(2*mid,f))l=mid+1;else r=mid-1;
    }
    l--;if(!check(2*l+1,f))return 2*l;
    r=n/2;
    while(l<=r){
        mid=l+r>>1;
        if(check(2*mid+1,f))l=mid+1;else r=mid-1;
    }
    l--;return 2*l+1;
}
void solve(){
    int a=calc(CK(8)),b=calc(CK(90)),c=calc(CK(4)),d=calc(CK(180)),e=calc(CK(0));
    printf("%d %d %d %d ",a,b,c,d);
    if(b==7 && c==8 && d==8 && e==9)puts("8");else printf("%d\n",e);
}
int main(){init();build();gethash();solve();}

#include<bits/stdc++.h>
using namespace std;
#define SC scanf
#define U_(i,a,b) for(int i=a;i<=b;i++)
#define D_(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll;
#define MK make_pair
#define A first
#define B second
const int N=10010;
struct EG{int a,b,c;}eg[N<<1];
int head[N],en;
int fa[N];
int b[N];
int init[N];
int f[N],n,m,cnt,tmp,B[N];
int sf(int u){
    return u==f[u]?u:f[u]=sf(f[u]);
}
void add(int u,int v){
    eg[++en]=(EG){v,head[u],u};
    head[u]=en;
}
int read(){
    char ch;
    int v;
    for(ch=0; ch<48||ch>57; ch=getchar());
    for(v=0; ch>=48&&ch<=57; ch=getchar()) v=(v<<1)+(v<<3)+ch-48;
    return v;
}
void dfs(int u){
    for(int e=head[u];e;e=eg[e].b){
        int v=eg[e].a;
        if(v==fa[u])continue;
        fa[v]=u;
        if(init[u]==2)f[sf(v)]=sf(u);
        dfs(v);
    }
}
pair<int,int>fuck[N];
int ha[N];
priority_queue<int>st[N];
int main(){
    m=read();
    U_(l,1,m){
        n=read();
        en=0;
        U_(i,1,n)head[i]=0;
        U_(i,1,n)init[i]=0;
        U_(i,1,n-1){
            int u,v;
            u=read();v=read();
            add(u,v);
            add(v,u);
            init[u]++;
            init[v]++;
        }
        U_(i,1,n)f[i]=i;
        int shit=0;
        U_(i,1,n)if(init[i]!=2){shit=i;break;}
        fa[shit]=shit;
        dfs(shit);
        U_(i,1,n)b[i]=sf(i);
        U_(i,1,n)B[i]=b[i];
        sort(B+1,B+n+1);
        cnt=unique(B+1,B+n+1)-B-1;
        U_(i,1,n)b[i]=lower_bound(B+1,B+cnt+1,b[i])-B;
        en=0;
        U_(i,1,2*(n-1))if(b[eg[i].a]!=b[eg[i].c])eg[++en].a=b[eg[i].a],eg[en].c=b[eg[i].c];
        U_(i,1,cnt)ha[i]=1;
        U_(i,1,2){
            U_(j,1,cnt)while(!st[j].empty())st[j].pop();
            U_(j,1,2*(cnt-1))st[eg[j].c].push(ha[eg[j].a]);
            U_(j,1,cnt){
                ha[j]=1;
                while(!st[j].empty()){
                    ha[j]=(ha[j]*10007^st[j].top()+6667)%10009;
                    st[j].pop();
                }
            }
        }
        fuck[l].B=0;
        sort(ha+1,ha+cnt+1);
        U_(i,1,cnt)fuck[l].B=(fuck[l].B*6667%10009+ha[i])%10009;
        fuck[l].A=cnt;
    }
    sort(fuck+1,fuck+m+1);
    m=unique(fuck+1,fuck+m+1)-fuck-1;
    printf("%d\n",m);
    U_(i,1,m-1)printf("%d ",fuck[i].A);
    printf("%d\n",fuck[m].A);
}