[题解放博客了](https://foreverlasting1202.github.io/2019/09/10/BJUnitedRound3%E4%B8%89%E8%89%B2%E6%A0%91/)
一道计数好题。
<!--more-->
首先考虑一件事，无标号无根树怎么处理。
有个经典的做法就是利用重心，可以强制重心为根，然后减去这些多余情况就好了。由于一棵树可能会有两个重心，那就把连接重心的那条边作为根看就好了。
然后回到这道题，把题目变成无标号有根树。
于是考虑枚举根的颜色和根的度数，然后暴力转移。意思就是，设$R[n][d]$为根颜色为$red$，度数为$d$，有$n$个点的方案数。同理有另外两个。然后转移$d$的时候，就是枚举第一棵子树有几个点，第二棵子树有几个这样，这样做是$O(n^3)$的（因为只有当点为整棵树的根时才用枚举到$4$，否则到$3$就好了）。
发现瓶颈在转移，容易发现这个转移可以容斥，于是复杂度就降到了$O(n^2)$。具体容斥以及转移看代码就好了，虽然我也是看了半天别人代码才懂的。。。
code:
```cpp
//2019.9.10 by ljz
//email
[email protected]
//if you find any bug in my code
//please tell me
#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
//using namespace __gnu_cxx;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f
#define unl __int128
#define eps 5.6e-8
#define RG register
#define db double
#define pc(x) __builtin_popcount(x)
#define ctz(x) __builtin_ctz(x)
//#define pc(x) __builtin_popcountll(x)
typedef pair<int,int> Pair;
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pb push_back
#define ull unsigned LL
#define lowbit(x) (x&-x)
#define gc getchar
//template <class T>using Tree=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
//inline char gc() {
// static char buf[100000],*p1,*p2;
// return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
//}
inline int read() {
res s=0,ch=gc();
while(ch<'0'||ch>'9')ch=gc();
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
return s;
}
//inline int read() {
// res s=0,ch=gc(),w=1;
// while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
// while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
// return s*w;
//}
inline LL Read() {
RG LL s=0;
res ch=gc();
while(ch<'0'||ch>'9')ch=gc();
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
return s;
}
//inline LL Read() {
// RG LL s=0;
// res ch=gc(),w=1;
// while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
// while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
// return s*w;
//}
//inline void write(RG unl x){
// if(x>10)write(x/10);
// putchar(int(x%10)+'0');
//}
inline void swap(res &x,res &y) {
x^=y^=x^=y;
}
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//clock_t start=clock();
//inline void ck(){
// if(1.0*(clock()-start)/CLOCKS_PER_SEC>0.1)exit(0);
//}
const int N=3e3+10;
namespace MAIN{
int kcz;
inline void add(res &x,const res &y){
x+=y,x>=kcz?x-=kcz:(x<0?x+=kcz:1);
}
inline int Add(const res &x,const res &y){
return x+y>=kcz?x+y-kcz:(x+y<0?x+y+kcz:x+y);
}
inline int mul(const res &x,const res &y){
return int(1LL*x*y%kcz);
}
inline int mul(const res &x,const res &y,const res &d){
return int(1LL*x*y/d%kcz);
}
inline int qpow(res x,res y){
res ret=1;
while(y){
if(y&1)ret=mul(ret,x);
x=mul(x,x),y>>=1;
}
return ret;
}
int inv[5];
int R[N][5],B[N][4],Y[N][4];
int dp[N],br[N];
int nn;
inline int get(const RG LL &x){
return Add(int(x%kcz),0);
}
inline void DP(const res &n){
if(n==1){
R[1][0]=B[1][0]=Y[1][0]=1;
if(nn>2)br[1]=2,dp[1]=3;
return;
}
//R 1
R[n][1]=dp[n-1];
//R 2
for(res i=1;i+i<=n-1;i++)i==n-1-i?add(R[n][2],mul(dp[i],dp[i]+1,2)):add(R[n][2],mul(dp[i],dp[n-1-i]));
//R 3
res ret=0,val=(n-1)%3?0:dp[(n-1)/3];
for(res i=3;i<=n-1;i++)add(R[n][3],mul(R[i][2],dp[n-i]));
for(res i=1;i+i<n-1;i++)i==n-1-i*2?add(ret,mul(dp[i],dp[i]-1)):add(ret,mul(dp[i],dp[n-1-i*2]));
R[n][3]=Add(int((1LL*mul(get(1LL*R[n][3]-ret*2-val),inv[3])+ret+val)%kcz),0);
//B 1
B[n][1]=dp[n-1];
//B 2
B[n][2]=R[n][2];
//Y 1
Y[n][1]=br[n-1];
//Y 2
for(res i=1;i+i<=n-1;i++)i==n-1-i?add(Y[n][2],mul(br[i],br[i]+1,2)):add(Y[n][2],mul(br[i],br[n-1-i]));
if(n*2<nn)br[n]=int((1LL*R[n][1]+R[n][2]+R[n][3]+B[n][1]+B[n][2])%kcz),dp[n]=int((1LL*br[n]+Y[n][1]+Y[n][2])%kcz);
}
int n;
inline void MAIN(){
nn=n=read(),kcz=read(),inv[0]=inv[1]=1;
if(n==1){puts("3");return;}
if(n==2){puts("5");return;}
for(res i=2;i<=4;i++)inv[i]=mul(inv[kcz%i],kcz-kcz/i);
for(res i=1;i<=n;i++)DP(i);
//R 4
res ret=0,Ret=0,REt=0,val=(n-1)%4?0:dp[(n-1)/4];
for(res i=3;i<n;i++)add(R[n][4],mul(R[i][3],dp[n-i]));
for(res i=1;i*3<n-1;i++)i==n-1-i*3?add(ret,mul(dp[i],dp[i]-1)):add(ret,mul(dp[i],dp[n-1-i*3]));
if(n&1)for(res i=1;i+i<=(n-1)/2;i++)i==(n-1)/2-i?add(Ret,mul(dp[i],dp[i]-1,2)):add(Ret,mul(dp[i],dp[(n-1)/2-i]));
for(res i=1;i+i<=n-3;i++)add(REt,mul(dp[i],R[n-i*2][2]));
add(REt,kcz-(Add(Add(val,ret),Add(Ret,Ret))));
R[n][4]=Add(int((1LL*get(1LL*R[n][4]-val-mul(Add(ret,Ret),2)-mul(REt,3))*inv[4]%kcz+val+ret+Ret+REt)%kcz),0);
//B 3
B[n][3]=R[n][3];
//Y 3
ret=0,val=(n-1)%3?0:br[(n-1)/3];
for(res i=3;i<=n-1;i++)add(Y[n][3],mul(Y[i][2],br[n-i]));
for(res i=1;i+i<n-1;i++)i==n-1-i*2?add(ret,mul(br[i],br[i]-1)):add(ret,mul(br[i],br[n-1-i*2]));
Y[n][3]=Add(int((1LL*get(1LL*Y[n][3]-ret*2-val)*inv[3]%kcz+ret+val)%kcz),0);
res i=n/2;
br[i]=int((1LL*R[i][1]+R[i][2]+R[i][3]+B[i][1]+B[i][2])%kcz),dp[i]=int((1LL*br[i]+Y[i][1]+Y[i][2])%kcz);
dp[n]=int((1LL*R[n][2]+R[n][3]+B[n][2]+Y[n][2])%kcz);
res ans=Add(Add(dp[n],R[n][4]),Add(B[n][3],Y[n][3]));
if(n%2==0)add(ans,Add(mul(dp[n/2],br[n/2]),kcz-mul(br[n/2],br[n/2]-1,2)));
printf("%d\n",ans);
}
}
int main(){
// srand(19260817);
// freopen("signin.in","r",stdin);
// freopen("signin.out","w",stdout);
MAIN::MAIN();
return 0;
}
```