自动搬运

查看原文

来自洛谷，原作者为

	Yajnun **

搬运于2025-08-24 22:03:30，当前版本为作者最后更新于2019-10-11 19:50:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

状压dp，需要一定代码能力

对于每个子树，枚举其左边k个叶子和右边k个叶子的联通情况，其余的叶子节点不是路径端点状态。每个叶子节点共有四种情况。

1. 不是路径的端点。（记为0）
2. 是子树根所在路径的端点。（记为1，合法状态中该节点个数小于等于2）
3. 不与任何点相连，单独组成一种路径。（记为-1）
4. 是非子树根所在路径路径的端点。（每条路径记为一种颜色）

预处理出状态两两之间的转移情况。只考虑左右子树叶子节点之间连边情况即可。之后直接进行树形dp即可。统计答案时，枚举最左k个叶子和最右k个叶子的连边情况即可。（当叶子总数小于等于2k时，由于叶子之间连边会被重复计算，只能将链缩为一个点后直接暴力）。具体详见代码。

k=3，合法状态数共有2665种。左右状态叶子个数均大于等于6时，转移共有201536种。可以通过。

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<iostream>
#include<map>
#include<cstring>
#define ll long long
#define maxn 1005
#define p 998244353 
#define re(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
inline int read(){char c=getchar();int f=1;int ans = 0;while(c>'9'||c<'0'){if(c=='-')f=-f;c=getchar();}while(c<='9'&&c>='0'){ans =ans*10+c-'0';c=getchar();}return ans*f;}
//_____________________________________________________________________________________________________
int k,used[maxn],_n,n,m,_a[maxn][maxn],__a[maxn][maxn],leaf[maxn],_st[maxn];
ll ans;
inline int dfs1(int x)//缩链
{
    int cnt = 0,y;
    re(i,1,_n)
        if(_a[x][i])
            cnt++;
    if(cnt==1)
    {
        re(i,1,_n)
            if(_a[x][i])
                return dfs1(i);
    }
    used[x] = 1;
    if(!cnt)
    {
        _st[++_st[0]] = ++n;
        leaf[n]=1;
        return n;
    }
    int _x = ++n;
    re(i,1,_n)
        if(_a[x][i])
        {
            int y = dfs1(i);
            leaf[_x] += leaf[y] ;
            if(used[i])
                __a[_x][y] = 1;
            else
            {
                leaf[++n] = leaf[y];
                __a[_x][n] = __a[n][y] = 1;
            }
        }
    return _x; 
}
inline void build()
{
    re(i,1,_n)
        if(_a[1][i])
        {
            int y = dfs1(i);
            leaf[1] += leaf[y];
            if(used[i])
                __a[1][y] = 1;
            else
            {
                leaf[++n]=leaf[y];
                __a[1][n] = __a[n][y] = 1;
            }
        }
}
int __dp[1<<21][25];
inline void solve1()//暴力
{
    ans = 0;
    re(i,1,_st[0])
        re(j,1,k)
            __a[ _st[i] ][ _st[ i+j>_st[0] ? i+j-_st[0] : i+j ] ] = 1;
    re(i,1,n)
        re(j,1,n)
            if(__a[i][j])
                __a[j][i] = 1;
    int S = (1<<n)-1;__dp[1][1] = 1;
    for(int s=1;s<=S;s+=2)
        re(x,1,n)
            if(__dp[s][x]&&((s>>x-1)&1))
                re(y,1,n)
                    if(__a[x][y]&&(((s>>y-1)&1)==0))
                        (__dp[ s|(1<<y-1) ][y] += __dp[s][x])%=p;
    re(i,1,n)
        if(__a[1][i])
            (ans+=__dp[S][i])%=p;
    printf("%d\n",ans*(p+1)/2%p);
}
//______________________________________________
int match[40];
struct node
{
    int len,root;
    int s[13];
    inline void clear()
    {
        re(i,1,13)
            s[i] = 0;
        len = root = 0;
    }
    void pri()
    {
        printf("%d|",root);
        re(i,1,len)
            printf("%d ",s[i]);
        printf("\n________________________\n");
    };
    inline bool operator <(node x)const
    {
        if(root!=x.root ) return root<x.root ;
        if(len!=x.len) return len<x.len ;
        re(i,1,len)
            if(s[i]!=x.s [i])
                return s[i] < x.s [i];
        return false;
    }
    inline void sort(int sz)
    {
        int cnt = 1;
        re(i,2,sz)
            match[i] = 0;
        re(i,1,len)
            if( s[i]>1 )
            {
                if( match[s[i]] )
                    s[i] = match[s[i]];
                else
                    s[i] = match[s[i]] = ++cnt;
            }
    }
}node1,a[maxn*40];
map<node,int> mp;
int tot;
void dfs2(int i,int cnt)
{
    if(i==node1.len +1)
    {
        re(j,1,node1.len )
            if(node1.s [j])
            {
                a[++tot] = node1;
                mp[node1] = tot;
                break;
            }
        return ;
    }
    dfs2(i+1,cnt);
    if(!node1.s [i])
    {
        node1.s[i] = cnt+1;
        re(j,i+1,node1.len )
            if(!node1.s [j])
            {
                node1.s [j] = cnt+1;
                dfs2(i+1,cnt+1);
                node1.s [j] = 0;
            }
        node1.s [i] = 0; 
    }
}
struct turn
{
    int x,y,to;
    turn(int x=0,int y=0,int to=0)
    :x(x),y(y),to(to){};
}f[7][7][210000];
int tot_f[7][7];
#define pr pair<int,int> 
int st1[maxn*200],_st2;
pr st2[maxn*200];
inline void check(node x,int cnt)
{
    re(i,k+1,x.len-k)
        if(x.s [i])
            return;
    node1.clear(); 
    if(x.len>2*k)
    {
        node1.root = x.root ;
        node1.len = 2*k;
        re(i,1,k)
            node1.s [i] = x.s[i];
        re(i,x.len -k+1,x.len )
            node1.s [i- x.len  + 2*k] = x.s[i] ;
    }
    else node1 = x; 
    node1.sort(cnt);
    if( mp[node1]!=0 )
        st1[++st1[0]] = mp[node1];
}
int vis[20];
inline void dfs3(int i,int lim,node x,int cnt)
{
    if(i==lim+1)
    {
        check(x,cnt+1);
        return ;
    }
    dfs3(i+1,lim,x,cnt+1);
    if(x.s [i]>0)
        re(j,lim+1,min(x.len ,i+k))
        {
            int n_col = x.s [j]==1 || x.s[i] == 1 ? 1 : cnt+1;
            if(x.s [j]>0&&(x.s [j]!=x.s [i]||x.s[j]==1 ))
            {
                node1 = x;
                re(t,1,x.len )
                    if( x.s [t] == x.s [i] || x.s [t]==x.s [j] )
                        node1.s[t] = n_col;	
                node1.s [i] = node1.s [j] = 0;			
                dfs3(i+1,lim,node1,cnt+1);
            }
            if(x.s [j]==-1)
            {
                node1 = x;	
                node1.s [j] = node1.s [i];
                node1.s [i] = 0;
                dfs3(i+1,lim,node1,cnt+1);
            }
        }
    if(x.s [i]==-1)
        re(j,lim+1,min(x.len,i+k))
            if(x.s [j])
            {
                node1  = x;
                if(x.s [j]==-1)
                    node1.s [i] = node1.s [j] = cnt+1;
                else 
                    node1.s [i] = node1.s [j],
                    node1.s [j] = 0;
                dfs3(i+1,lim,node1,cnt+1);
                re(t,j+1,min(x.len,i+k))
                    if(x.s[t]==-1 ||(x.s[t]>0&&(x.s[t]!=x.s[j] || x.s[t]==1)))  
                    {
                        node1 = x;
                        node1.s [i] = 0;
                        if( x.s[j]==-1 && x.s[t] ==-1 )
                            node1.s [j] = node1.s [t] = cnt+1 ;
                        if( x.s[j]==-1 && x.s[t]!=-1)
                            node1.s [j] = node1.s [t] , node1.s [t] = 0;
                        if( x.s [j]!=-1&& x.s[t]==-1)
                            node1.s [t] = node1.s [j] , node1.s [j] = 0;
                        if( x.s [j]!=-1&&x.s[t]!=-1)
                        {
                            int n_col = x.s [j]==1 || x.s[t] == 1 ? 1 : cnt+1;
                            re(_t,1,x.len)
                                if(x.s[_t]==x.s[j]|| x.s[_t] == x.s[t] )
                                    node1.s [_t] = n_col ;
                            node1.s [j] = node1.s [t] = 0;
                        }
                        dfs3(i+1,lim,node1,cnt+1);	
                    }
            }
}
inline void Turn(node l,node r)
{
    if(l.root + r.root > 2)
        return;
    node1.clear();
    re(i,1,l.len )
        node1.s[i] = l.s [i];
    re(i,1,r.len )
        node1.s [ i+l.len ] = r.s [i] <=1 ? r.s [i] : r.s [i] + k ;
    node1.root = l.root + r.root ;
    node1.len = l.len + r.len ;
    dfs3( max(1,l.len -k+1),l.len , node1 ,2*k+1 );
}
inline int _Turn(int x)
{
    if(a[x].root == 0)
        return 0;
    if(a[x].root == 1)
        return x;
    node1 = a[x];
    node1.root = 0;
    re(i,1,node1.len )
        if(node1.s [i]==1)
            node1.s [i] = k+2;
    node1.sort(k+2);
    return mp[node1];
}
pr _f[maxn*40];int _tot_f,cnt_5;
ll dp[maxn][maxn*3],_dp[maxn*3];
inline ll count(int i,node x,int col)
{
    if(x.len !=2*k || x.root !=2)
        return 0;
    if(i==k+1)
    {
        re(t,1,2*k)
            if(x.s[t])
                return 0;
        return 1;
    }
    int cnt = 0;
    if(!x.s[i])
        cnt = count(i+1,x,col);
    if(x.s[i]>0)
        re(j,k+i,2*k)
            if(x.s[j])
            {
                node1 = x;
                if( x.s[j]>0 &&( x.s [j]==1 ||  x.s[i] !=x .s[j]))
                {
                    int n_col = x.s [i]==1 || x.s [j] ==1 ? 1 : col +1;
                    re(t,1,2*k)
                        if( x.s [t] == x.s[i] || x.s[t]== x.s[j] )
                            node1.s [t] = n_col;
                    node1.s [i] = node1.s [j] = 0;
                    cnt += count(i+1,node1,col+1);
                }
                if( x.s[j]==-1 )
                {
                    node1.s [j] =  node1.s [i];
                    node1.s [i] = 0;
                    cnt += count(i+1,node1,col+1);
                }
            }
    if(x.s[i]==-1)
    {
        re(j,k+i,2*k)
            if(x.s[j])
            {
                re(t,j+1,2*k)
                {
                    node1  =x;
                    if( x.s[t]==-1 ||(x.s[t]>0 && (x.s[t]==1|| x.s[t]!=x.s[j] )))
                    {
                        node1.s [i] = 0;
                        if( x.s[j]==-1 && x.s[t] ==-1 )
                            node1.s [j] = node1.s [t] = col+1;
                        if( x.s[j]==-1 && x.s[t]!=-1)
                            node1.s [j] = node1.s [t] , node1.s [t] = 0;
                        if( x.s [j]!=-1&& x.s[t]==-1)
                            node1.s [t] = node1.s [j] , node1.s [j] = 0;
                        if( x.s [j]!=-1&&x.s[t]!=-1)
                        {
                            int n_col = x.s [j]==1 || x.s[t] == 1 ? 1 : cnt+1;
                            re(_t,1,x.len)
                                    if(x.s[_t]==x.s[j]||x.s[_t]==x.s[t])
                                        node1.s [_t] = n_col ;
                            node1.s [j] = node1.s [t] = 0;
                        }
                        cnt += count( i+1,node1,col+1 );
                    }
                }
            }
    }
    return cnt;	
}
void dfs4(int x)
{
    int bo = 0,cnt_leaf=0;
    re(y,1,n)
        if(__a[x][y])
        {
            dfs4(y);
            if(!bo)
            {
                memcpy(dp[x],dp[y],sizeof(dp[x]));
                bo = 1;
                cnt_leaf = leaf[y];
            }
            else 
            {
                memcpy(_dp,dp[x],sizeof(_dp));
                memset(dp[x],0,sizeof(dp[x]));
                re(t,1,tot_f[ cnt_leaf ][ leaf[y] ])
                {
                    turn _ = f[ cnt_leaf ][ leaf[y] ][t] ; 
                    ( dp[x][ _.to ] += _dp[ _.x ] * dp[y][ _.y ])%=p;
                }
                cnt_leaf = min( cnt_leaf + leaf[y] , 2*k); 
			
		
             }
    	}
    if(!bo)
    {
        dp[x][1] = dp[x][2] = 1;
        return ;
    }
    if(x!=1)
    {	
       
        memcpy(_dp,dp[x],sizeof(_dp));
        memset(dp[x],0,sizeof(dp[x]));
        re(t,1,_tot_f)
            ( dp[x][ _f[t].second ] += _dp[ _f[t].first ] )%=p ;
    }
    else
        re(t,1,tot)
        {
           ( ans += count(1,a[t],k+1) * dp[x][t] )%=p;
       }
}
int main()
{
	//freopen("0.in","r",stdin);
    _n = read(),k=read();
    re(i,2,_n)
        _a[read()][i] = 1;
    n = 1;
    build();
    re(i,1,n)
    	leaf[i] = min( leaf[i],2*k );
    if(n<=21)
    {
     solve1();  
	 return 0;
    }
    re(i,1,2*k)
    {
        node1.len = i;
        re(s,0,(1<<i)-1)
        {
            re(w,1,i)
                node1.s [w] = - ((s>>w-1)&1);
            node1.root = 0;
            dfs2(1,1);
            re(j,1,i)
                if(node1.s [j]!=-1)
                {
                    node1.root  = 1;
                    node1.s [j] = 1;
                    dfs2(1,1);
                    node1.root = 2;
                    re(k,j+1,i)
                        if(node1.s [k]!=-1)
                        {
                            node1.s[k] = 1;
                            dfs2(1,1);
                            node1.s[k] = 0;
                        }
                    node1.s[j]=0;
                }	
        }
    }			
    node1.clear();
    node1.root = 2;
    node1.len = k*2;
    a[++tot] = node1;
    mp[node1] = tot;
    re(i,1,tot)
        re(j,1,tot)
        {
            st1[0] = 0;
            Turn(a[i],a[j]);            
            if(st1[0])
      	      re(t,1,st1[0])
      	          f[ a[i].len ][ a[j].len ][ ++tot_f[a[i].len ][a[j].len ]] = turn(i,j,st1[t]);
       }
    re(i,1,tot)
    {
        int to = _Turn(i);
        if(to)
	    	_f[++_tot_f] = make_pair( i,to );
    }
    dfs4(1);
    printf("%lld\n",ans);
    return  0;
}