题目描述 Description
求一颗有根树/树形图的拓扑序个数.
输入描述 Input Description
第一行一个n和一个素数P,表示这颗树有n个节点,要求拓扑序个数modP之后的结果.
接下来n-1行,每行有两个数字x和y,表示x是y的父亲.
保证1<=n<=1500000, n<P<2^31,P为质数.
输出描述 Output Description
一行一个数字,为该树形图拓扑序个数modP的结果.
样例输入 Sample Input
样例1 4 100000007 1 2 1 3 2 4
样例2 6 100000007 1 2 2 3 1 4 3 5 5 6
样例输出 Sample Output
样例1 3
样例2 5
数据范围及提示 Data Size & Hint
每个非根节点的儿子个数平均较多,数据量较大,建议c/c++选手才用scanf的读入方式
#include<iostream>
#include<cstring>
#include<cstdio> using namespace std; int md; long long gcd(long long y3)
{
long long x1 = ,x2 = ,y1 = ,y2 = ,x3 = md,t1,t2,t3,q;
while()
{
if (y3==) return y2;
q=x3/y3;
t1=x1-q*y1,t2=x2-q*y2,t3=x3-q*y3;
x1 = y1,x2 = y2,x3 = y3;
y1 = t1,y2 = t2,y3 = t3;
}
} long long an[];
//long long bn[1510000];
long long n;
struct edge
{
int v,next;
}edge[];
int head[],e = ;
void increase(int u,int v)
{
edge[e].v = v;
edge[e].next = head[u];
head[u] = e++;
}
int cn[];
long long ans[];
bool rd[]; void dfs(int k)
{
cn[k] = ans[k] = ;
for(int t = head[k];t!=;t = edge[t].next)
{
int v = edge[t].v;
if(!cn[v]) dfs(v);
cn[k]+=cn[v];
ans[k] = ans[k]*(gcd(an[cn[v]])+md)%md*ans[v]%md;
}
ans[k] = ans[k]*an[cn[k]-]%md;
}
int Scan()
{
char ch;
int a = ;
while((ch = getchar())>=)
{
a = *a+ch-;
}
return a;
} int main()
{
n = Scan(),md = Scan();
long long i,j,k;
//an[0] = bn[0] = 1;
an[] = ;
for(i = ;i<=n;i++)
{
an[i] = an[i-]*i%md;
//bn[i] = bn[i-1]*(gcd(i)+md)%md;
}
for(i = ;i<n;i++)
{
int a,b;
a = Scan(),b = Scan();
rd[b]|=;
increase(a,b);
}
int fa;
for(i = ;i<=n;i++)
if(!rd[i])
{
fa = i;
break;
}
dfs(fa);
cout<<ans[fa]<<endl;
return ;
}