题目大意

这道题从G题（Operating on a Graph ）延伸而来，附上G题大意：
给一个 n 个点的 Graph，第 i 个点一刚开始是第 I 种颜色，接着有 k 次操作，第 i 次操作有个参数 oi 代表颜色 oi 会侵略所有和自己相邻的颜色，于是所有和 oi 相邻的颜色全都变成 oi (若已没有颜色oi 已被侵略，则该次操作无效)，求最终每个点的颜色。

给出一棵具有n个顶点的树。设p是从0到n-1的排列，定义函数f(p)：p是输入运算符序列，f(p)是满足条件的操作数：执行第i个操作时，至少有一个顶点属于o[i]组。
令S为从0到n-1的所有可能排列的集合。 请计算

官方题解的解释：
给一个n个点的树定义一个排列的花费为，把该序列当作G题的 a 序列，有多少次侵略行为中树上至少有一个是第oi种颜色。
计算所有0~n-1的排列的花费总和 mod 998244353。

 解题思路

我们把每个点分为两类：好点在一个排列中会对答案有贡献1，坏点没有贡献。
可以分析得出，好点和坏点有一些性质，满足这些的组合就是合法的：
不存在两个相邻好点，每个坏点至少和一个比他大的好点相邻。

这样就可以用一个树形dp来解决了。
这里用dp1储存组合个数，dp2储存所有组合的花费和。存储方法：
dp1/dp2 [子树树根编号]  [子树里有多少点比树根大]  [树根是好点 / 坏点但尚未有比它大的好点相邻 / 坏点已有比它大的好点相邻]

列出转移式中要用到连续和的技巧。当一棵子树接在另一棵子树下時，有
[ 树根是好点，坏点但尚未有比它大的好点相邻，坏点已有比它大的好点相邻 ]
这三种情况，又分别有
[ 树根是好点，坏点但尚未有比它大的好点相邻，坏点已有比它大的好点相邻 ]
三种情况，乘起来共九种，要全部考虑。

AC代码 


#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
vector<int> v[2010];
int a[2010],b[2010][2010],dp1[2010][3][2010],dp2[2010][3][2010],t1[3][2010],t2[3][2010],n;
int get(int x[],int l,int r)
{
    if(l>r) return 0;
    if(l==0) return x[r];
	int t=x[r]-x[l-1];
	t+=mod*(t<0);
    return t;
}
void sum(int x,int y,int t,int u,int v,int e,int f,int l,int r)
{
	t1[t][e+f]=(t1[t][e+f]+1ll*dp1[x][u][e]*get(dp1[y][v],l,r)%mod*b[e+f][e]%mod*b[(a[x]-e-1)+(a[y]-f)][a[y]-f])%mod;
    t2[t][e+f]=(t2[t][e+f]+1ll*dp2[x][u][e]*get(dp1[y][v],l,r)%mod*b[e+f][e]%mod*b[(a[x]-e-1)+(a[y]-f)][a[y]-f])%mod;
	t2[t][e+f]=(t2[t][e+f]+1ll*dp1[x][u][e]*get(dp2[y][v],l,r)%mod*b[e+f][e]%mod*b[(a[x]-e-1)+(a[y]-f)][a[y]-f])%mod;
}
void dfs(int x)
{
	int t,i,j,k;
    dp1[x][1][0]=dp2[x][1][0]=dp2[x][0][0]=0;
    dp1[x][0][0]=dp1[x][2][0]=dp2[x][2][0]=a[x]=1;
    for(k=0;k<v[x].size();k++)
	{
		t=v[x][k];
        dfs(t);
        for(i=0;i<3;i++)
		{
            memset(t1[i],0,sizeof(int)*(a[x]+a[t]));
            memset(t2[i],0,sizeof(int)*(a[x]+a[t]));
        }
        for(i=0;i<a[x];i++)
            for(j=0;j<=a[t];j++)
			{
                sum(x,t,2,2,1,i,j,0,a[t]-1);
                sum(x,t,2,2,0,i,j,j,a[t]-1);
                sum(x,t,1,1,2,i,j,0,a[t]-1);
                sum(x,t,1,1,1,i,j,0,a[t]-1);
                sum(x,t,1,0,2,i,j,0,j-1);
                sum(x,t,0,0,2,i,j,j,a[t]-1);
                sum(x,t,0,0,1,i,j,0,a[t]-1);
            }
        a[x]+=a[t];
        for(i=0;i<3;i++)
		{
            memcpy(dp1[x][i],t1[i],sizeof(int)*a[x]);
            memcpy(dp2[x][i],t2[i],sizeof(int)*a[x]);
        }
    }
    for(i=0;i<3;i++) 
        for(j=1;j<a[x];j++)
		{
            dp1[x][i][j]=(dp1[x][i][j]+dp1[x][i][j-1])%mod;
            dp2[x][i][j]=(dp2[x][i][j]+dp2[x][i][j-1])%mod;
        }
}
int main()
{
    int t,ans,x,i,j;
    for(i=0;i<2000;i++)
	{
        b[i][0]=1;
        for(j=1;j<=i;j++)
            b[i][j]=(b[i-1][j-1]+b[i-1][j])%mod;
    }
    scanf("%d",&t);
    while(t--)
    {
    	ans=0;
    	scanf("%d",&n);
	    for(i=0;i<n;i++)
			v[i].clear();
	    for(i=1;i<n;i++)
		{
	        scanf("%d",&x);
	        v[x].push_back(i);
	    }
	    dfs(0);
	    ans=(ans+dp2[0][1][n-1]+dp2[0][2][n-1])%mod;
	    printf("%d\n",ans);
	}
    return 0;
}