提出 #45322143

---

ソースコード 拡げる

#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<bitset>
#include<cassert>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(((long long)(n))-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();++itr)
#define pb push_back
#define mk make_pair
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define spln(i,n) (i==n?'\n':' ')
#define fac_init(n){fac[0]=fac[1]=inv[1]=fi[0]=fi[1]=1;fz(i,2,n){fac[i]=1ll*fac[i-1]*i%mod;inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;fi[i]=1ll*fi[i-1]*inv[i]%mod;}}
using namespace std;
typedef long long i64;
typedef long double f80;
typedef unsigned int u32;
typedef unsigned long long u64;
//typedef __int128 i128;
//typedef unsigned __int128 u128;
#ifndef ONLINE_JUDGE
	FILE *___=freopen("1.in","r",stdin);
#endif
inline void read(int &x)
{
	char c;int f=1;
	while(!isdigit(c=getchar()))if(c=='-')f=-1;
	x=(c&15);while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);
	x*=f;
}
const int mod=998244353;
int n,m,i,j,k,typ[155],cc[2],ans;
vector<int> bi[155];
void dfs1(int x,int p)
{
	cc[typ[x]=typ[p]^1]++;
	ff(bi[x],it)if(*it!=p){
		dfs1(*it,x);
	}
}
int f[155][305][2][2],nf[305][2][2];
void dfs2(int x,int p)
{
	f[x][typ[x]==1?n+1:n-1][0][0]=1;int i,j,a,b,c,d;
	ff(bi[x],it)if(*it!=p){
		dfs2(*it,x);memset(nf,0,sizeof(nf));
		fz(i,-n,n)fz0k(a,2)fz0k(b,2)if(f[x][i+n][a][b]){
			if(typ[*it]==0){
				nf[i+n][1][b]=(nf[i+n][1][b]+f[x][i+n][a][b])%mod;
			}
			else{
				nf[i+n][a][1]=(nf[i+n][a][1]+f[x][i+n][a][b])%mod;
			}
			fz(j,-n,n)fz0k(c,2)fz0k(d,2)if(f[*it][j+n][c][d]){
				nf[i+j+n][a|c][b|d]=(nf[i+j+n][a|c][b|d]+1ll*f[x][i+n][a][b]*f[*it][j+n][c][d])%mod;
			}
		}
		memcpy(f[x],nf,sizeof(nf));
	}
	fz0k(a,2)fz0k(b,2){
		if(!a&&(!p||typ[p]!=0)) continue;
		if(!b&&(!p||typ[p]!=1)) continue;
		ans=(ans+f[x][n+cc[1]-cc[0]][a][b])%mod;
	}
}
int sz0[155],sz1[155];
int dfn[155],dfe[155],mp[155],ti;
void dfs3(int x,int p)
{
	sz0[x]=sz1[x]=0;
	if(typ[x]==1) sz1[x]++; else sz0[x]++;
	mp[dfn[x]=++ti]=x;
	ff(bi[x],it)if(*it!=p){
		dfs3(*it,x);
		sz0[x]+=sz0[*it];
		sz1[x]+=sz1[*it];
	}
	dfe[x]=ti;
}
void dfs5(int x,int p)
{
	sz0[x]=sz1[x]=0;
	if(typ[x]==1) sz1[x]++; else sz0[x]++;
	ff(bi[x],it)if(*it!=p){
		dfs5(*it,x);
		sz0[x]+=sz0[*it];
		sz1[x]+=sz1[*it];
	}
}
bool dfs4(int x,int p,int c0,int c1)
{
	if(typ[x]==1) c1++; else c0++;
	c0--;c1--;
	int s0=0,s1=0;bool lf=1;
	ff(bi[x],it)if(*it!=p){
		s0+=sz0[*it];
		s1+=sz1[*it];
		lf=0;
	}
	if(lf) return 0;
	if(typ[x]==1){
		if(c1==0) return 1;
	}
	else{
		if(c0==0) return 1;
	}
	ff(bi[x],it)if(*it!=p){
		if(dfs4(*it,x,c0+s0-sz0[*it],c1+s1-sz1[*it])) return 1;
	}
	return 0;
}
int dp[155][155][155][2];
int res[155][155];
void solve(int nd)
{
	memset(dp,0,sizeof(dp));int c0=0,c1=0,i,j,k,p;
	dp[1][0][0][0]=1;
	fz(i,2,ti){
		int x=mp[i],to=dfe[x];
		fz0g(j,c0)fz0g(k,c1)fz0k(p,2)if(dp[i-1][j][k][p]){
			dp[i][j][k][p]=(dp[i][j][k][p]+dp[i-1][j][k][p])%mod;
			dp[to][j+sz0[x]][k+sz1[x]][p|(typ[x]==nd)]=(dp[to][j+sz0[x]][k+sz1[x]][p|(typ[x]==nd)]+dp[i-1][j][k][p])%mod;
		}
		c0+=(typ[x]==0);c1+=(typ[x]==1);
	}
	fz0g(j,c0)fz0g(k,c1){
		res[j][k]=(res[j][k]+dp[ti][j][k][1])%mod;
	}
}
int main()
{
	read(n);fz1(i,n-1){int x,y;read(x);read(y);bi[x].push_back(y);bi[y].push_back(x);}
	dfs1(1,0);
	if(cc[0]==cc[1]) ans=(ans+1)%mod;
	ans=(ans+1)%mod;
	dfs2(1,0);
	fz1(i,n){
		ff(bi[i],it){
			ti=0;fz1(j,n)dfn[j]=0;
			dfs3(i,*it);
			memset(res,0,sizeof(res));
			solve(typ[i]);
			int c0=0,c1=0;
			fz1(j,n)if(!dfn[j]){
				if(typ[j])c1++;
				else c0++;
			}
			dfs5(*it,i);
			fz0g(j,n)fz0g(k,n)if(res[j][k]&&j+c0==k+c1){
				if(dfs4(*it,i,j,k)){
					ans=(ans-res[j][k]+mod)%mod;
				}
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

提出情報

ジャッジ結果