NOI批量评测 - 记录详情

#	状态分数	耗时	内存占用
#1	Accepted 4	2ms	788 KiB
#2	Accepted 4	2ms	788 KiB
#3	Accepted 4	2ms	788 KiB
#4	Accepted 4	178ms	33 MiB
#5	Accepted 4	178ms	32.9 MiB
#6	Accepted 4	186ms	32.9 MiB
#7	Accepted 4	199ms	32.9 MiB
#8	Accepted 4	189ms	33 MiB
#9	Accepted 4	174ms	33 MiB
#10	Accepted 4	183ms	33 MiB
#11	Accepted 4	2ms	920 KiB
#12	Accepted 4	2ms	832 KiB
#13	Accepted 4	2ms	788 KiB
#14	Accepted 4	2ms	788 KiB
#15	Accepted 4	2ms	916 KiB
#16	Accepted 4	199ms	35.2 MiB
#17	Accepted 4	187ms	35.2 MiB
#18	Accepted 4	147ms	35.4 MiB
#19	Accepted 4	106ms	11 MiB
#20	Accepted 4	102ms	11 MiB
#21	Accepted 4	106ms	11 MiB
#22	Accepted 4	27ms	6 MiB
#23	Accepted 4	27ms	6 MiB
#24	Accepted 4	192ms	23.2 MiB
#25	Accepted 4	199ms	23.2 MiB
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define gc (zz==ZZ&&(zz=(ZZ=buf)+fread(buf,1,1<<20,stdin),zz==ZZ)?EOF:*ZZ++)
char buf[1<<20],*zz{buf},*ZZ{buf};
template<typename Tp>
inline void read(Tp &x) {
    x=0;char ch(gc);
    while(ch<=32) {
        ch=gc;
    }
    while(ch>32) {
        x=(x<<3)+(x<<1)+(ch^48),ch=gc;
    }
}
#undef gc
typedef unsigned int uint;
typedef unsigned long long ull;
constexpr uint mod{1000000007};
constexpr uint plus(const uint &x,const uint &y) {
    if(x+y>=mod) {
        return x+y-mod;
    }
    return x+y;
}
constexpr uint minus(const uint &x,const uint &y) {
    if(x<y) {
        return x-y+mod;
    }
    return x-y;
}
constexpr void add(uint &x,const uint &y) {
    x=plus(x,y);
}
constexpr void sub(uint &x,const uint &y) {
    x=minus(x,y);
}
constexpr void mul_add(uint &x,const uint &y,const uint &z) {
    x=(x+ull(y)*z)%mod;
}
constexpr uint power(uint x,uint y) {
    uint s{1};
    while(y>0) {
        if(y&1) {
            s=ull(s)*x%mod;
        }
        x=ull(x)*x%mod;
        y>>=1;
    }
    return s;
}
constexpr int N{100000};
uint fac[N+5];
inline void init() {
    fac[0]=1;
    for(int i=1;i<=N;i++) {
        fac[i]=ull(fac[i-1])*i%mod;
    }
}
int deg[N+5];
int ed[N+5][3];
struct edge {
    int v,w,next;
};
edge e[(N<<1)+5];
int en,last[N+5];
inline void add_edge(const int &u,const int &v,const int &w) {
    e[++en]={v,w,last[u]},last[u]=en;
    e[++en]={u,w,last[v]},last[v]=en;
}
int fa[N+5];
// 0: u
// 1: if the edge between u and fa[u] is one of the two endpoints
// 2: if there is a valid root in the subtree of u
// 3: if the position of root is determined, 0: not, 1: out of the subtree, 2: in the subtree
uint dp[N+5][2][2][3];
void dfs(const int &u) {
    int dg{0};
    // 0: number of endpoints
    // 1: if there is a valid root
    // 2: if the position of root is determined
    uint aux[3][2][3]{},aux2[3][2][3]{};
    aux[0][0][0]=1;
    for(int i=last[u];i;i=e[i].next) {
        int &v{e[i].v},&w{e[i].w};
        if(v==fa[u]) {
            continue;
        }
        fa[v]=u,dfs(v),++dg;
        std::memset(aux2,0,sizeof(aux2));
        if(w==0) {
            if(aux[0][0][0]!=0) {
                mul_add(aux2[1][0][2],aux[0][0][0],dp[v][0][0][0]);
                mul_add(aux2[1][0][2],aux[0][0][0],dp[v][0][0][1]);
                mul_add(aux2[1][0][2],aux[0][0][0],dp[v][0][0][2]);
                mul_add(aux2[1][1][2],aux[0][0][0],dp[v][0][1][0]);
                mul_add(aux2[1][1][2],aux[0][0][0],dp[v][0][1][1]);
                mul_add(aux2[1][1][2],aux[0][0][0],dp[v][0][1][2]);
                mul_add(aux2[0][0][1],aux[0][0][0],dp[v][1][0][0]);
                mul_add(aux2[1][0][0],aux[0][0][0],dp[v][1][0][0]);
                mul_add(aux2[0][0][1],aux[0][0][0],dp[v][1][0][1]);
                mul_add(aux2[1][0][1],aux[0][0][0],dp[v][1][0][1]);
                mul_add(aux2[1][0][2],aux[0][0][0],dp[v][1][0][2]);
                mul_add(aux2[0][0][1],aux[0][0][0],dp[v][1][1][0]);
                mul_add(aux2[1][1][0],aux[0][0][0],dp[v][1][1][0]);
                mul_add(aux2[0][0][1],aux[0][0][0],dp[v][1][1][1]);
                mul_add(aux2[1][1][1],aux[0][0][0],dp[v][1][1][1]);
                mul_add(aux2[1][1][2],aux[0][0][0],dp[v][1][1][2]);
            }
            if(aux[0][0][1]!=0) {
                mul_add(aux2[1][0][2],aux[0][0][1],dp[v][0][0][0]);
                mul_add(aux2[1][0][2],aux[0][0][1],dp[v][0][0][1]);
                mul_add(aux2[1][0][2],aux[0][0][1],dp[v][0][0][2]);
                mul_add(aux2[1][1][2],aux[0][0][1],dp[v][0][1][0]);
                mul_add(aux2[1][1][2],aux[0][0][1],dp[v][0][1][1]);
                mul_add(aux2[1][1][2],aux[0][0][1],dp[v][0][1][2]);
                mul_add(aux2[0][0][1],aux[0][0][1],dp[v][1][0][0]);
                mul_add(aux2[1][0][1],aux[0][0][1],dp[v][1][0][0]);
                mul_add(aux2[0][0][1],aux[0][0][1],dp[v][1][0][1]);
                mul_add(aux2[1][0][1],aux[0][0][1],dp[v][1][0][1]);
                mul_add(aux2[1][0][2],aux[0][0][1],dp[v][1][0][2]);
                mul_add(aux2[0][0][1],aux[0][0][1],dp[v][1][1][0]);
                mul_add(aux2[1][1][1],aux[0][0][1],dp[v][1][1][0]);
                mul_add(aux2[0][0][1],aux[0][0][1],dp[v][1][1][1]);
                mul_add(aux2[1][1][1],aux[0][0][1],dp[v][1][1][1]);
                mul_add(aux2[1][1][2],aux[0][0][1],dp[v][1][1][2]);
            }
            if(aux[0][0][2]!=0) {
                mul_add(aux2[0][0][2],aux[0][0][2],dp[v][1][0][0]);
                mul_add(aux2[1][0][2],aux[0][0][2],dp[v][1][0][0]);
                mul_add(aux2[0][0][2],aux[0][0][2],dp[v][1][0][1]);
                mul_add(aux2[1][0][2],aux[0][0][2],dp[v][1][0][1]);
                mul_add(aux2[0][0][2],aux[0][0][2],dp[v][1][1][0]);
                mul_add(aux2[1][0][2],aux[0][0][2],dp[v][1][1][0]);
                mul_add(aux2[0][0][2],aux[0][0][2],dp[v][1][1][1]);
                mul_add(aux2[1][0][2],aux[0][0][2],dp[v][1][1][1]);
            }
            if(aux[0][1][0]!=0) {
                mul_add(aux2[1][0][2],aux[0][1][0],dp[v][0][0][0]);
                mul_add(aux2[1][0][2],aux[0][1][0],dp[v][0][0][1]);
                mul_add(aux2[1][0][2],aux[0][1][0],dp[v][0][0][2]);
                mul_add(aux2[1][1][2],aux[0][1][0],dp[v][0][1][0]);
                mul_add(aux2[1][1][2],aux[0][1][0],dp[v][0][1][1]);
                mul_add(aux2[1][1][2],aux[0][1][0],dp[v][0][1][2]);
                mul_add(aux2[0][1][1],aux[0][1][0],dp[v][1][0][0]);
                mul_add(aux2[1][1][0],aux[0][1][0],dp[v][1][0][0]);
                mul_add(aux2[0][1][1],aux[0][1][0],dp[v][1][0][1]);
                mul_add(aux2[1][1][1],aux[0][1][0],dp[v][1][0][1]);
                mul_add(aux2[1][0][2],aux[0][1][0],dp[v][1][0][2]);
                mul_add(aux2[0][1][1],aux[0][1][0],dp[v][1][1][0]);
                mul_add(aux2[1][1][0],aux[0][1][0],dp[v][1][1][0]);
                mul_add(aux2[0][1][1],aux[0][1][0],dp[v][1][1][1]);
                mul_add(aux2[1][1][1],aux[0][1][0],dp[v][1][1][1]);
                mul_add(aux2[1][1][2],aux[0][1][0],dp[v][1][1][2]);
            }
            if(aux[0][1][1]!=0) {
                mul_add(aux2[1][0][2],aux[0][1][1],dp[v][0][0][0]);
                mul_add(aux2[1][0][2],aux[0][1][1],dp[v][0][0][1]);
                mul_add(aux2[1][0][2],aux[0][1][1],dp[v][0][0][2]);
                mul_add(aux2[1][1][2],aux[0][1][1],dp[v][0][1][0]);
                mul_add(aux2[1][1][2],aux[0][1][1],dp[v][0][1][1]);
                mul_add(aux2[1][1][2],aux[0][1][1],dp[v][0][1][2]);
                mul_add(aux2[0][1][1],aux[0][1][1],dp[v][1][0][0]);
                mul_add(aux2[1][1][1],aux[0][1][1],dp[v][1][0][0]);
                mul_add(aux2[0][1][1],aux[0][1][1],dp[v][1][0][1]);
                mul_add(aux2[1][1][1],aux[0][1][1],dp[v][1][0][1]);
                mul_add(aux2[1][0][2],aux[0][1][1],dp[v][1][0][2]);
                mul_add(aux2[0][1][1],aux[0][1][1],dp[v][1][1][0]);
                mul_add(aux2[1][1][1],aux[0][1][1],dp[v][1][1][0]);
                mul_add(aux2[0][1][1],aux[0][1][1],dp[v][1][1][1]);
                mul_add(aux2[1][1][1],aux[0][1][1],dp[v][1][1][1]);
                mul_add(aux2[1][1][2],aux[0][1][1],dp[v][1][1][2]);
            }
            if(aux[0][1][2]!=0) {
                mul_add(aux2[0][1][2],aux[0][1][2],dp[v][1][0][0]);
                mul_add(aux2[1][1][2],aux[0][1][2],dp[v][1][0][0]);
                mul_add(aux2[0][1][2],aux[0][1][2],dp[v][1][0][1]);
                mul_add(aux2[1][1][2],aux[0][1][2],dp[v][1][0][1]);
                mul_add(aux2[0][1][2],aux[0][1][2],dp[v][1][1][0]);
                mul_add(aux2[1][1][2],aux[0][1][2],dp[v][1][1][0]);
                mul_add(aux2[0][1][2],aux[0][1][2],dp[v][1][1][1]);
                mul_add(aux2[1][1][2],aux[0][1][2],dp[v][1][1][1]);
            }
            if(aux[1][0][0]!=0) {
                mul_add(aux2[2][0][2],aux[1][0][0],dp[v][0][0][0]);
                mul_add(aux2[2][0][2],aux[1][0][0],dp[v][0][0][1]);
                mul_add(aux2[2][0][2],aux[1][0][0],dp[v][0][0][2]);
                mul_add(aux2[2][1][2],aux[1][0][0],dp[v][0][1][0]);
                mul_add(aux2[2][1][2],aux[1][0][0],dp[v][0][1][1]);
                mul_add(aux2[2][1][2],aux[1][0][0],dp[v][0][1][2]);
                mul_add(aux2[1][0][1],aux[1][0][0],dp[v][1][0][0]);
                mul_add(aux2[2][0][0],aux[1][0][0],dp[v][1][0][0]);
                mul_add(aux2[1][0][1],aux[1][0][0],dp[v][1][0][1]);
                mul_add(aux2[2][0][1],aux[1][0][0],dp[v][1][0][1]);
                mul_add(aux2[2][0][2],aux[1][0][0],dp[v][1][0][2]);
                mul_add(aux2[1][0][1],aux[1][0][0],dp[v][1][1][0]);
                mul_add(aux2[2][1][0],aux[1][0][0],dp[v][1][1][0]);
                mul_add(aux2[1][0][1],aux[1][0][0],dp[v][1][1][1]);
                mul_add(aux2[2][1][1],aux[1][0][0],dp[v][1][1][1]);
                mul_add(aux2[2][1][2],aux[1][0][0],dp[v][1][1][2]);
            }
            if(aux[1][0][1]!=0) {
                mul_add(aux2[2][0][2],aux[1][0][1],dp[v][0][0][0]);
                mul_add(aux2[2][0][2],aux[1][0][1],dp[v][0][0][1]);
                mul_add(aux2[2][0][2],aux[1][0][1],dp[v][0][0][2]);
                mul_add(aux2[2][1][2],aux[1][0][1],dp[v][0][1][0]);
                mul_add(aux2[2][1][2],aux[1][0][1],dp[v][0][1][1]);
                mul_add(aux2[2][1][2],aux[1][0][1],dp[v][0][1][2]);
                mul_add(aux2[1][0][1],aux[1][0][1],dp[v][1][0][0]);
                mul_add(aux2[2][0][1],aux[1][0][1],dp[v][1][0][0]);
                mul_add(aux2[1][0][1],aux[1][0][1],dp[v][1][0][1]);
                mul_add(aux2[2][0][1],aux[1][0][1],dp[v][1][0][1]);
                mul_add(aux2[2][0][2],aux[1][0][1],dp[v][1][0][2]);
                mul_add(aux2[1][0][1],aux[1][0][1],dp[v][1][1][0]);
                mul_add(aux2[2][1][1],aux[1][0][1],dp[v][1][1][0]);
                mul_add(aux2[1][0][1],aux[1][0][1],dp[v][1][1][1]);
                mul_add(aux2[2][1][1],aux[1][0][1],dp[v][1][1][1]);
                mul_add(aux2[2][1][2],aux[1][0][1],dp[v][1][1][2]);
            }
            if(aux[1][0][2]!=0) {
                mul_add(aux2[1][0][2],aux[1][0][2],dp[v][1][0][0]);
                mul_add(aux2[2][0][2],aux[1][0][2],dp[v][1][0][0]);
                mul_add(aux2[1][0][2],aux[1][0][2],dp[v][1][0][1]);
                mul_add(aux2[2][0][2],aux[1][0][2],dp[v][1][0][1]);
                mul_add(aux2[1][0][2],aux[1][0][2],dp[v][1][1][0]);
                mul_add(aux2[2][0][2],aux[1][0][2],dp[v][1][1][0]);
                mul_add(aux2[1][0][2],aux[1][0][2],dp[v][1][1][1]);
                mul_add(aux2[2][0][2],aux[1][0][2],dp[v][1][1][1]);
            }
            if(aux[1][1][0]!=0) {
                mul_add(aux2[2][0][2],aux[1][1][0],dp[v][0][0][0]);
                mul_add(aux2[2][0][2],aux[1][1][0],dp[v][0][0][1]);
                mul_add(aux2[2][0][2],aux[1][1][0],dp[v][0][0][2]);
                mul_add(aux2[2][1][2],aux[1][1][0],dp[v][0][1][0]);
                mul_add(aux2[2][1][2],aux[1][1][0],dp[v][0][1][1]);
                mul_add(aux2[2][1][2],aux[1][1][0],dp[v][0][1][2]);
                mul_add(aux2[1][1][1],aux[1][1][0],dp[v][1][0][0]);
                mul_add(aux2[2][1][0],aux[1][1][0],dp[v][1][0][0]);
                mul_add(aux2[1][1][1],aux[1][1][0],dp[v][1][0][1]);
                mul_add(aux2[2][1][1],aux[1][1][0],dp[v][1][0][1]);
                mul_add(aux2[2][0][2],aux[1][1][0],dp[v][1][0][2]);
                mul_add(aux2[1][1][1],aux[1][1][0],dp[v][1][1][0]);
                mul_add(aux2[2][1][0],aux[1][1][0],dp[v][1][1][0]);
                mul_add(aux2[1][1][1],aux[1][1][0],dp[v][1][1][1]);
                mul_add(aux2[2][1][1],aux[1][1][0],dp[v][1][1][1]);
                mul_add(aux2[2][1][2],aux[1][1][0],dp[v][1][1][2]);
            }
            if(aux[1][1][1]!=0) {
                mul_add(aux2[2][0][2],aux[1][1][1],dp[v][0][0][0]);
                mul_add(aux2[2][0][2],aux[1][1][1],dp[v][0][0][1]);
                mul_add(aux2[2][0][2],aux[1][1][1],dp[v][0][0][2]);
                mul_add(aux2[2][1][2],aux[1][1][1],dp[v][0][1][0]);
                mul_add(aux2[2][1][2],aux[1][1][1],dp[v][0][1][1]);
                mul_add(aux2[2][1][2],aux[1][1][1],dp[v][0][1][2]);
                mul_add(aux2[1][1][1],aux[1][1][1],dp[v][1][0][0]);
                mul_add(aux2[2][1][1],aux[1][1][1],dp[v][1][0][0]);
                mul_add(aux2[1][1][1],aux[1][1][1],dp[v][1][0][1]);
                mul_add(aux2[2][1][1],aux[1][1][1],dp[v][1][0][1]);
                mul_add(aux2[2][0][2],aux[1][1][1],dp[v][1][0][2]);
                mul_add(aux2[1][1][1],aux[1][1][1],dp[v][1][1][0]);
                mul_add(aux2[2][1][1],aux[1][1][1],dp[v][1][1][0]);
                mul_add(aux2[1][1][1],aux[1][1][1],dp[v][1][1][1]);
                mul_add(aux2[2][1][1],aux[1][1][1],dp[v][1][1][1]);
                mul_add(aux2[2][1][2],aux[1][1][1],dp[v][1][1][2]);
            }
            if(aux[1][1][2]!=0) {
                mul_add(aux2[1][1][2],aux[1][1][2],dp[v][1][0][0]);
                mul_add(aux2[2][1][2],aux[1][1][2],dp[v][1][0][0]);
                mul_add(aux2[1][1][2],aux[1][1][2],dp[v][1][0][1]);
                mul_add(aux2[2][1][2],aux[1][1][2],dp[v][1][0][1]);
                mul_add(aux2[1][1][2],aux[1][1][2],dp[v][1][1][0]);
                mul_add(aux2[2][1][2],aux[1][1][2],dp[v][1][1][0]);
                mul_add(aux2[1][1][2],aux[1][1][2],dp[v][1][1][1]);
                mul_add(aux2[2][1][2],aux[1][1][2],dp[v][1][1][1]);
            }
            if(aux[2][0][0]!=0) {
                mul_add(aux2[2][0][1],aux[2][0][0],dp[v][1][0][0]);
                mul_add(aux2[2][0][1],aux[2][0][0],dp[v][1][0][1]);
                mul_add(aux2[2][0][1],aux[2][0][0],dp[v][1][1][0]);
                mul_add(aux2[2][0][1],aux[2][0][0],dp[v][1][1][1]);
            }
            if(aux[2][0][1]!=0) {
                mul_add(aux2[2][0][1],aux[2][0][1],dp[v][1][0][0]);
                mul_add(aux2[2][0][1],aux[2][0][1],dp[v][1][0][1]);
                mul_add(aux2[2][0][1],aux[2][0][1],dp[v][1][1][0]);
                mul_add(aux2[2][0][1],aux[2][0][1],dp[v][1][1][1]);
            }
            if(aux[2][0][2]!=0) {
                mul_add(aux2[2][0][2],aux[2][0][2],dp[v][1][0][0]);
                mul_add(aux2[2][0][2],aux[2][0][2],dp[v][1][0][1]);
                mul_add(aux2[2][0][2],aux[2][0][2],dp[v][1][1][0]);
                mul_add(aux2[2][0][2],aux[2][0][2],dp[v][1][1][1]);
            }
            if(aux[2][1][0]!=0) {
                mul_add(aux2[2][1][1],aux[2][1][0],dp[v][1][0][0]);
                mul_add(aux2[2][1][1],aux[2][1][0],dp[v][1][0][1]);
                mul_add(aux2[2][1][1],aux[2][1][0],dp[v][1][1][0]);
                mul_add(aux2[2][1][1],aux[2][1][0],dp[v][1][1][1]);
            }
            if(aux[2][1][1]!=0) {
                mul_add(aux2[2][1][1],aux[2][1][1],dp[v][1][0][0]);
                mul_add(aux2[2][1][1],aux[2][1][1],dp[v][1][0][1]);
                mul_add(aux2[2][1][1],aux[2][1][1],dp[v][1][1][0]);
                mul_add(aux2[2][1][1],aux[2][1][1],dp[v][1][1][1]);
            }
            if(aux[2][1][2]!=0) {
                mul_add(aux2[2][1][2],aux[2][1][2],dp[v][1][0][0]);
                mul_add(aux2[2][1][2],aux[2][1][2],dp[v][1][0][1]);
                mul_add(aux2[2][1][2],aux[2][1][2],dp[v][1][1][0]);
                mul_add(aux2[2][1][2],aux[2][1][2],dp[v][1][1][1]);
            }
        }
        else {
            if(aux[0][0][0]!=0) {
                mul_add(aux2[1][0][2],aux[0][0][0],dp[v][0][0][0]);
                mul_add(aux2[1][0][2],aux[0][0][0],dp[v][0][0][1]);
                mul_add(aux2[1][0][2],aux[0][0][0],dp[v][0][0][2]);
                mul_add(aux2[1][1][2],aux[0][0][0],dp[v][0][1][0]);
                mul_add(aux2[1][1][2],aux[0][0][0],dp[v][0][1][1]);
                mul_add(aux2[1][1][2],aux[0][0][0],dp[v][0][1][2]);
                mul_add(aux2[0][0][1],aux[0][0][0],dp[v][1][0][0]);
                mul_add(aux2[1][1][0],aux[0][0][0],dp[v][1][0][0]);
                mul_add(aux2[0][0][1],aux[0][0][0],dp[v][1][0][1]);
                mul_add(aux2[1][1][1],aux[0][0][0],dp[v][1][0][1]);
                mul_add(aux2[1][0][2],aux[0][0][0],dp[v][1][0][2]);
                mul_add(aux2[0][0][1],aux[0][0][0],dp[v][1][1][0]);
                mul_add(aux2[1][1][0],aux[0][0][0],dp[v][1][1][0]);
                mul_add(aux2[0][0][1],aux[0][0][0],dp[v][1][1][1]);
                mul_add(aux2[1][1][1],aux[0][0][0],dp[v][1][1][1]);
                mul_add(aux2[1][1][2],aux[0][0][0],dp[v][1][1][2]);
            }
            if(aux[0][0][1]!=0) {
                mul_add(aux2[1][0][2],aux[0][0][1],dp[v][0][0][0]);
                mul_add(aux2[1][0][2],aux[0][0][1],dp[v][0][0][1]);
                mul_add(aux2[1][0][2],aux[0][0][1],dp[v][0][0][2]);
                mul_add(aux2[1][1][2],aux[0][0][1],dp[v][0][1][0]);
                mul_add(aux2[1][1][2],aux[0][0][1],dp[v][0][1][1]);
                mul_add(aux2[1][1][2],aux[0][0][1],dp[v][0][1][2]);
                mul_add(aux2[0][0][1],aux[0][0][1],dp[v][1][0][0]);
                mul_add(aux2[1][1][1],aux[0][0][1],dp[v][1][0][0]);
                mul_add(aux2[0][0][1],aux[0][0][1],dp[v][1][0][1]);
                mul_add(aux2[1][1][1],aux[0][0][1],dp[v][1][0][1]);
                mul_add(aux2[1][0][2],aux[0][0][1],dp[v][1][0][2]);
                mul_add(aux2[0][0][1],aux[0][0][1],dp[v][1][1][0]);
                mul_add(aux2[1][1][1],aux[0][0][1],dp[v][1][1][0]);
                mul_add(aux2[0][0][1],aux[0][0][1],dp[v][1][1][1]);
                mul_add(aux2[1][1][1],aux[0][0][1],dp[v][1][1][1]);
                mul_add(aux2[1][1][2],aux[0][0][1],dp[v][1][1][2]);
            }
            if(aux[0][0][2]!=0) {
                mul_add(aux2[0][0][2],aux[0][0][2],dp[v][1][0][0]);
                mul_add(aux2[1][0][2],aux[0][0][2],dp[v][1][0][0]);
                mul_add(aux2[0][0][2],aux[0][0][2],dp[v][1][0][1]);
                mul_add(aux2[1][0][2],aux[0][0][2],dp[v][1][0][1]);
                mul_add(aux2[0][0][2],aux[0][0][2],dp[v][1][1][0]);
                mul_add(aux2[1][0][2],aux[0][0][2],dp[v][1][1][0]);
                mul_add(aux2[0][0][2],aux[0][0][2],dp[v][1][1][1]);
                mul_add(aux2[1][0][2],aux[0][0][2],dp[v][1][1][1]);
            }
            if(aux[0][1][0]!=0) {
                mul_add(aux2[1][0][2],aux[0][1][0],dp[v][0][0][0]);
                mul_add(aux2[1][0][2],aux[0][1][0],dp[v][0][0][1]);
                mul_add(aux2[1][0][2],aux[0][1][0],dp[v][0][0][2]);
                mul_add(aux2[1][1][2],aux[0][1][0],dp[v][0][1][0]);
                mul_add(aux2[1][1][2],aux[0][1][0],dp[v][0][1][1]);
                mul_add(aux2[1][1][2],aux[0][1][0],dp[v][0][1][2]);
                mul_add(aux2[0][1][1],aux[0][1][0],dp[v][1][0][0]);
                mul_add(aux2[1][1][0],aux[0][1][0],dp[v][1][0][0]);
                mul_add(aux2[0][1][1],aux[0][1][0],dp[v][1][0][1]);
                mul_add(aux2[1][1][1],aux[0][1][0],dp[v][1][0][1]);
                mul_add(aux2[1][0][2],aux[0][1][0],dp[v][1][0][2]);
                mul_add(aux2[0][1][1],aux[0][1][0],dp[v][1][1][0]);
                mul_add(aux2[1][1][0],aux[0][1][0],dp[v][1][1][0]);
                mul_add(aux2[0][1][1],aux[0][1][0],dp[v][1][1][1]);
                mul_add(aux2[1][1][1],aux[0][1][0],dp[v][1][1][1]);
                mul_add(aux2[1][1][2],aux[0][1][0],dp[v][1][1][2]);
            }
            if(aux[0][1][1]!=0) {
                mul_add(aux2[1][0][2],aux[0][1][1],dp[v][0][0][0]);
                mul_add(aux2[1][0][2],aux[0][1][1],dp[v][0][0][1]);
                mul_add(aux2[1][0][2],aux[0][1][1],dp[v][0][0][2]);
                mul_add(aux2[1][1][2],aux[0][1][1],dp[v][0][1][0]);
                mul_add(aux2[1][1][2],aux[0][1][1],dp[v][0][1][1]);
                mul_add(aux2[1][1][2],aux[0][1][1],dp[v][0][1][2]);
                mul_add(aux2[0][1][1],aux[0][1][1],dp[v][1][0][0]);
                mul_add(aux2[1][1][1],aux[0][1][1],dp[v][1][0][0]);
                mul_add(aux2[0][1][1],aux[0][1][1],dp[v][1][0][1]);
                mul_add(aux2[1][1][1],aux[0][1][1],dp[v][1][0][1]);
                mul_add(aux2[1][0][2],aux[0][1][1],dp[v][1][0][2]);
                mul_add(aux2[0][1][1],aux[0][1][1],dp[v][1][1][0]);
                mul_add(aux2[1][1][1],aux[0][1][1],dp[v][1][1][0]);
                mul_add(aux2[0][1][1],aux[0][1][1],dp[v][1][1][1]);
                mul_add(aux2[1][1][1],aux[0][1][1],dp[v][1][1][1]);
                mul_add(aux2[1][1][2],aux[0][1][1],dp[v][1][1][2]);
            }
            if(aux[0][1][2]!=0) {
                mul_add(aux2[0][1][2],aux[0][1][2],dp[v][1][0][0]);
                mul_add(aux2[1][1][2],aux[0][1][2],dp[v][1][0][0]);
                mul_add(aux2[0][1][2],aux[0][1][2],dp[v][1][0][1]);
                mul_add(aux2[1][1][2],aux[0][1][2],dp[v][1][0][1]);
                mul_add(aux2[0][1][2],aux[0][1][2],dp[v][1][1][0]);
                mul_add(aux2[1][1][2],aux[0][1][2],dp[v][1][1][0]);
                mul_add(aux2[0][1][2],aux[0][1][2],dp[v][1][1][1]);
                mul_add(aux2[1][1][2],aux[0][1][2],dp[v][1][1][1]);
            }
            if(aux[1][0][0]!=0) {
                mul_add(aux2[2][0][2],aux[1][0][0],dp[v][0][0][0]);
                mul_add(aux2[2][0][2],aux[1][0][0],dp[v][0][0][1]);
                mul_add(aux2[2][0][2],aux[1][0][0],dp[v][0][0][2]);
                mul_add(aux2[2][1][2],aux[1][0][0],dp[v][0][1][0]);
                mul_add(aux2[2][1][2],aux[1][0][0],dp[v][0][1][1]);
                mul_add(aux2[2][1][2],aux[1][0][0],dp[v][0][1][2]);
                mul_add(aux2[1][0][1],aux[1][0][0],dp[v][1][0][0]);
                mul_add(aux2[2][1][0],aux[1][0][0],dp[v][1][0][0]);
                mul_add(aux2[1][0][1],aux[1][0][0],dp[v][1][0][1]);
                mul_add(aux2[2][1][1],aux[1][0][0],dp[v][1][0][1]);
                mul_add(aux2[2][0][2],aux[1][0][0],dp[v][1][0][2]);
                mul_add(aux2[1][0][1],aux[1][0][0],dp[v][1][1][0]);
                mul_add(aux2[2][1][0],aux[1][0][0],dp[v][1][1][0]);
                mul_add(aux2[1][0][1],aux[1][0][0],dp[v][1][1][1]);
                mul_add(aux2[2][1][1],aux[1][0][0],dp[v][1][1][1]);
                mul_add(aux2[2][1][2],aux[1][0][0],dp[v][1][1][2]);
            }
            if(aux[1][0][1]!=0) {
                mul_add(aux2[2][0][2],aux[1][0][1],dp[v][0][0][0]);
                mul_add(aux2[2][0][2],aux[1][0][1],dp[v][0][0][1]);
                mul_add(aux2[2][0][2],aux[1][0][1],dp[v][0][0][2]);
                mul_add(aux2[2][1][2],aux[1][0][1],dp[v][0][1][0]);
                mul_add(aux2[2][1][2],aux[1][0][1],dp[v][0][1][1]);
                mul_add(aux2[2][1][2],aux[1][0][1],dp[v][0][1][2]);
                mul_add(aux2[1][0][1],aux[1][0][1],dp[v][1][0][0]);
                mul_add(aux2[2][1][1],aux[1][0][1],dp[v][1][0][0]);
                mul_add(aux2[1][0][1],aux[1][0][1],dp[v][1][0][1]);
                mul_add(aux2[2][1][1],aux[1][0][1],dp[v][1][0][1]);
                mul_add(aux2[2][0][2],aux[1][0][1],dp[v][1][0][2]);
                mul_add(aux2[1][0][1],aux[1][0][1],dp[v][1][1][0]);
                mul_add(aux2[2][1][1],aux[1][0][1],dp[v][1][1][0]);
                mul_add(aux2[1][0][1],aux[1][0][1],dp[v][1][1][1]);
                mul_add(aux2[2][1][1],aux[1][0][1],dp[v][1][1][1]);
                mul_add(aux2[2][1][2],aux[1][0][1],dp[v][1][1][2]);
            }
            if(aux[1][0][2]!=0) {
                mul_add(aux2[1][0][2],aux[1][0][2],dp[v][1][0][0]);
                mul_add(aux2[2][0][2],aux[1][0][2],dp[v][1][0][0]);
                mul_add(aux2[1][0][2],aux[1][0][2],dp[v][1][0][1]);
                mul_add(aux2[2][0][2],aux[1][0][2],dp[v][1][0][1]);
                mul_add(aux2[1][0][2],aux[1][0][2],dp[v][1][1][0]);
                mul_add(aux2[2][0][2],aux[1][0][2],dp[v][1][1][0]);
                mul_add(aux2[1][0][2],aux[1][0][2],dp[v][1][1][1]);
                mul_add(aux2[2][0][2],aux[1][0][2],dp[v][1][1][1]);
            }
            if(aux[1][1][0]!=0) {
                mul_add(aux2[2][0][2],aux[1][1][0],dp[v][0][0][0]);
                mul_add(aux2[2][0][2],aux[1][1][0],dp[v][0][0][1]);
                mul_add(aux2[2][0][2],aux[1][1][0],dp[v][0][0][2]);
                mul_add(aux2[2][1][2],aux[1][1][0],dp[v][0][1][0]);
                mul_add(aux2[2][1][2],aux[1][1][0],dp[v][0][1][1]);
                mul_add(aux2[2][1][2],aux[1][1][0],dp[v][0][1][2]);
                mul_add(aux2[1][1][1],aux[1][1][0],dp[v][1][0][0]);
                mul_add(aux2[2][1][0],aux[1][1][0],dp[v][1][0][0]);
                mul_add(aux2[1][1][1],aux[1][1][0],dp[v][1][0][1]);
                mul_add(aux2[2][1][1],aux[1][1][0],dp[v][1][0][1]);
                mul_add(aux2[2][0][2],aux[1][1][0],dp[v][1][0][2]);
                mul_add(aux2[1][1][1],aux[1][1][0],dp[v][1][1][0]);
                mul_add(aux2[2][1][0],aux[1][1][0],dp[v][1][1][0]);
                mul_add(aux2[1][1][1],aux[1][1][0],dp[v][1][1][1]);
                mul_add(aux2[2][1][1],aux[1][1][0],dp[v][1][1][1]);
                mul_add(aux2[2][1][2],aux[1][1][0],dp[v][1][1][2]);
            }
            if(aux[1][1][1]!=0) {
                mul_add(aux2[2][0][2],aux[1][1][1],dp[v][0][0][0]);
                mul_add(aux2[2][0][2],aux[1][1][1],dp[v][0][0][1]);
                mul_add(aux2[2][0][2],aux[1][1][1],dp[v][0][0][2]);
                mul_add(aux2[2][1][2],aux[1][1][1],dp[v][0][1][0]);
                mul_add(aux2[2][1][2],aux[1][1][1],dp[v][0][1][1]);
                mul_add(aux2[2][1][2],aux[1][1][1],dp[v][0][1][2]);
                mul_add(aux2[1][1][1],aux[1][1][1],dp[v][1][0][0]);
                mul_add(aux2[2][1][1],aux[1][1][1],dp[v][1][0][0]);
                mul_add(aux2[1][1][1],aux[1][1][1],dp[v][1][0][1]);
                mul_add(aux2[2][1][1],aux[1][1][1],dp[v][1][0][1]);
                mul_add(aux2[2][0][2],aux[1][1][1],dp[v][1][0][2]);
                mul_add(aux2[1][1][1],aux[1][1][1],dp[v][1][1][0]);
                mul_add(aux2[2][1][1],aux[1][1][1],dp[v][1][1][0]);
                mul_add(aux2[1][1][1],aux[1][1][1],dp[v][1][1][1]);
                mul_add(aux2[2][1][1],aux[1][1][1],dp[v][1][1][1]);
                mul_add(aux2[2][1][2],aux[1][1][1],dp[v][1][1][2]);
            }
            if(aux[1][1][2]!=0) {
                mul_add(aux2[1][1][2],aux[1][1][2],dp[v][1][0][0]);
                mul_add(aux2[2][1][2],aux[1][1][2],dp[v][1][0][0]);
                mul_add(aux2[1][1][2],aux[1][1][2],dp[v][1][0][1]);
                mul_add(aux2[2][1][2],aux[1][1][2],dp[v][1][0][1]);
                mul_add(aux2[1][1][2],aux[1][1][2],dp[v][1][1][0]);
                mul_add(aux2[2][1][2],aux[1][1][2],dp[v][1][1][0]);
                mul_add(aux2[1][1][2],aux[1][1][2],dp[v][1][1][1]);
                mul_add(aux2[2][1][2],aux[1][1][2],dp[v][1][1][1]);
            }
            if(aux[2][0][0]!=0) {
                mul_add(aux2[2][0][1],aux[2][0][0],dp[v][1][0][0]);
                mul_add(aux2[2][0][1],aux[2][0][0],dp[v][1][0][1]);
                mul_add(aux2[2][0][1],aux[2][0][0],dp[v][1][1][0]);
                mul_add(aux2[2][0][1],aux[2][0][0],dp[v][1][1][1]);
            }
            if(aux[2][0][1]!=0) {
                mul_add(aux2[2][0][1],aux[2][0][1],dp[v][1][0][0]);
                mul_add(aux2[2][0][1],aux[2][0][1],dp[v][1][0][1]);
                mul_add(aux2[2][0][1],aux[2][0][1],dp[v][1][1][0]);
                mul_add(aux2[2][0][1],aux[2][0][1],dp[v][1][1][1]);
            }
            if(aux[2][0][2]!=0) {
                mul_add(aux2[2][0][2],aux[2][0][2],dp[v][1][0][0]);
                mul_add(aux2[2][0][2],aux[2][0][2],dp[v][1][0][1]);
                mul_add(aux2[2][0][2],aux[2][0][2],dp[v][1][1][0]);
                mul_add(aux2[2][0][2],aux[2][0][2],dp[v][1][1][1]);
            }
            if(aux[2][1][0]!=0) {
                mul_add(aux2[2][1][1],aux[2][1][0],dp[v][1][0][0]);
                mul_add(aux2[2][1][1],aux[2][1][0],dp[v][1][0][1]);
                mul_add(aux2[2][1][1],aux[2][1][0],dp[v][1][1][0]);
                mul_add(aux2[2][1][1],aux[2][1][0],dp[v][1][1][1]);
            }
            if(aux[2][1][1]!=0) {
                mul_add(aux2[2][1][1],aux[2][1][1],dp[v][1][0][0]);
                mul_add(aux2[2][1][1],aux[2][1][1],dp[v][1][0][1]);
                mul_add(aux2[2][1][1],aux[2][1][1],dp[v][1][1][0]);
                mul_add(aux2[2][1][1],aux[2][1][1],dp[v][1][1][1]);
            }
            if(aux[2][1][2]!=0) {
                mul_add(aux2[2][1][2],aux[2][1][2],dp[v][1][0][0]);
                mul_add(aux2[2][1][2],aux[2][1][2],dp[v][1][0][1]);
                mul_add(aux2[2][1][2],aux[2][1][2],dp[v][1][1][0]);
                mul_add(aux2[2][1][2],aux[2][1][2],dp[v][1][1][1]);
            }
        }
        std::memcpy(aux,aux2,sizeof(aux2));
    }
    std::memset(dp[u],0,sizeof(dp[u]));
    if(dg==0) {
        dp[u][1][0][0]=1;
        return;
    }
    for(int b=0;b<=1;b++) {
        for(int c=0;c<=2;c++) {
            add(dp[u][0][b][c],aux[2][b][c]);
        }
    }
    for(int b=0;b<=1;b++) {
        for(int c=0;c<=2;c++) {
            add(dp[u][1][b][c],aux[1][b][c]);
        }
    }
    for(int i=0;i<=1;i++) {
        for(int j=0;j<=1;j++) {
            for(int k=0;k<=2;k++) {
                dp[u][i][j][k]=ull(dp[u][i][j][k])*fac[dg-1]%mod;
            }
        }
    }
}
void solve() {
    int n,k;
    read(n),read(k);
    std::fill(deg+1,deg+n+1,0);
    for(int i=1;i<n;i++) {
        read(ed[i][0]),read(ed[i][1]);
        ++deg[ed[i][0]];
        ++deg[ed[i][1]];
        ed[i][2]=0;
    }
    for(int i=1;i<=k;i++) {
        int x;
        read(x);
        ed[x][2]=1;
    }
    std::fill(last+1,last+n+1,0),en=0;
    for(int i=1;i<n;i++) {
        add_edge(ed[i][0],ed[i][1],ed[i][2]);
    }
    std::fill(fa+1,fa+n+1,0);
    int rt{0};
    for(int i=1;i<=n;i++) {
        if(deg[i]==1) {
            rt=i;
            break;
        }
    }
    dfs(rt);
    uint ans{0};
    for(int j=0;j<=2;j++) {
        ans=plus(ans,dp[rt][1][1][j]);
    }
    printf("%u\n",ans);
}
int main() {
    freopen("traverse.in","r",stdin);
    freopen("traverse.out","w",stdout);
    init();
    int c,t;
    read(c),read(t);
    while(t--) {
        solve();
    }
    return 0;
}
/*
#include<stdio.h>
#include<algorithm>
int main() {
    freopen("1.out","w",stdout);
    for(int a=0;a<=2;a++) {
        for(int b=0;b<=1;b++) {
            for(int c=0;c<=2;c++) {
                printf("if(aux[%d][%d][%d]!=0) {\n",a,b,c);
                for(int i=0;i<=1;i++) {
                    for(int j=0;j<=1;j++) {
                        for(int k=0;k<=(c==2?1:2);k++) {
                            if(i==1&&k!=2) {
                                printf("    mul_add(aux2[%d][%d][%d],aux[%d][%d][%d],dp[v][%d][%d][%d]);\n",a,b,std::max(c,1),a,b,c,i,j,k);
                            }
                            if(a<2) {
                                if(i==0&&c<2) {
                                    printf("    mul_add(aux2[%d][%d][%d],aux[%d][%d][%d],dp[v][%d][%d][%d]);\n",a+1,j,2,a,b,c,i,j,k);
                                }
                                if(i==1) {
                                    printf("    mul_add(aux2[%d][%d][%d],aux[%d][%d][%d],dp[v][%d][%d][%d]);\n",a+1,(k<2&&b)||(c<2&&j)||(c<2&&k<2&&1),std::max(c,k),a,b,c,i,j,k);
                                }
                            }
                        }
                    }
                }
                printf("}\n");
            }
        }
    }
    return 0;
}
*/
递交者: CQ-0086
题目: NOIP2024CGF NOIP2024CGF
比赛: 【官方数据 CQ】 NOIP2024 批量测试
语言: C++14(O2)
代码长度: 31 KiB
递交时间: 2024-12-6 16:36:54
评测时间: 2024-12-6 17:01:24
分数: 100
总耗时: 2597ms
峰值时间: 199ms
峰值内存: 35.4 MiB
100 Accepted

代码

信息

100 Accepted

代码

信息

还没有账户？

登录
