题意：在一棵树上给所有点标号，要求任意一个子树里的点编号连续，每一个点的儿子编号连续。
分析：考虑到一个连续的序列[l,r]，如果这颗子树有超过3个非叶子儿子，那么一定是无解的。因为对于一个连续序列[l,r]最多可以分配给两个非叶子节点。分别是l和r，[l+1,r-1]这些可以随意分配给叶子节点。
考虑到这一点其实问题就可以简化了
对于每一个节点。
如果确定[l,r]是分配到以这个节点为根的子树，只有两种情况，分别是：l分配给该节点或者r分配给该节点，除此以外别无选择。
这样一来就很简单了。
假设以该节点为根的子树中，叶子儿子数为S，所有儿子方案的乘积记为T，
1.当非叶子儿子数等于0的时候，那么有两种分配方式（分配l或者r），因次该点方案数为2 * T * S!
2.当非叶子儿子数等于1的时候，那么也有两种分配方式（分配l或者r），因此该点方案数为2 * T * S!
3.当非叶子儿子数等于2的时候，那么也有两种分配方式（分配l或者r），但是发现这样会算重，把[l1,r1]分配给其中一个非叶子儿子，那么叶子儿子上的点是不能改变的，但是非叶子儿子处理的时候会多 * 2，因此该点方案数为 T * S!
代码：
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=100000+1000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
const LL mod=1e+9 + 7;
vector <int> e[MAXN];
LL dfs(int u,int fa){
int size=e[u].size();
int cnt0=0,cnt1=0;
for(int i=0;i<size;i++){
int v=e[u][i];
if(v!=fa){
if(e[v].size()==1)++cnt0;
else ++cnt1;
if(cnt1>2)return -1;
}
}
LL ss;
if(cnt1<2)ss=2;
else ss=1;
for(int i=0;i<size;i++){
int v=e[u][i];
if(v!=fa&&e[v].size()>1){
LL t=dfs(v,u);
if(t==-1)return -1;
ss*=t;
ss%=mod;
}
}
for(int i=2;i<=cnt0;i++){
ss=(ss*i)%mod;
}
return ss;
}
int main()
{
int t,n,cas=0;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
printf("Case #%d: ",++cas);
if(n==1){
puts("1");
continue;
}
for(int i=0;i<=n;i++)e[i].clear();
for(int i=0,x,y;i<n-1;i++){
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
LL ans=dfs(1,-1);
if(ans==-1)puts("0");
else printf("%I64d\n",ans);
}
return 0;
}
|
