QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#865267#9840. Tree PartitionMathew_MiaoRE 2ms10184kbC++202.8kb2025-01-21 16:21:422025-01-21 16:21:49

Judging History

你现在查看的是最新测评结果

  • [2025-01-21 16:21:49]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:10184kb
  • [2025-01-21 16:21:42]
  • 提交

answer

#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<numeric>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+10;
const int MAXM=405;
const int INF=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
int n,m;
int dp[MAXN][MAXM];
basic_string <int> tr[MAXN];
inline void add_edge(int x,int y){
	tr[x].push_back(y);
}
int dad[MAXN];
void dfs(int x){
	for(int to:tr[x])
	{
		if(to^dad[x]){
			dad[to]=x;
			dfs(to);
		}
	}
}
int top[2];
int st[2][MAXN];
int sum[2][MAXN][MAXM];
inline void push(int t,int p){
	top[t]++;
	st[t][top[t]]=p;
	int*s=sum[t][top[t]];
	memcpy(s,sum[t][top[t]-1],sizeof(int)*(m+1));
	for(int i=0;i<=m;i++)
	{
		s[i]+=dp[p-1][i];
		(s[i]>=mod)&&(s[i]-=mod);
	}
}
inline void add(int p){
	while(top[1]&&st[1][top[1]]>=p)
	{
		top[1]--;
	}
	basic_string <int> s;
	while(top[0]&&st[0][top[0]]>=p)
	{
		s.push_back(st[0][top[0]]);
		top[0]--;
	}
	reverse(s.begin(),s.end());
	for(int x:s)
	{
		push(1,x);
	}
}
int res[MAXM];
inline void qry(int t,int p){
	memset(res,0,sizeof(int)*(m+1));
	if(st[t][top[t]]<p){
		return ;
	}
	int l=1,r=top[t],mid;
	while(l<r)
	{
		mid=(l+r)>>1;
		if(st[t][mid]>=p){
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
	for(int i=0;i<=m;i++)
	{
		res[i]=sum[t][top[t]][i]-sum[t][l-1][i];
		(res[i]<0)&&(res[i]+=mod);
	}
}
set <int> bac;
inline void solve(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add_edge(x,y);
		add_edge(y,x);
	}
	dfs(1);
	dp[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		if(dad[i]>i){
			bac.insert(i);
		}
		for(int p:tr[i])
		{
			if(p<i&&dad[p]==i){
				bac.erase(p);
			}
		}
		for(int j=1;j<=m;j++)
		{
			dp[i][j]=dp[i-1][j-1];
		}
		int a=0,b=0;
		if(!bac.empty()){
			a=*prev(bac.end());
		}
		else{
			if(bac.size()>1){
				b=*prev(prev(bac.end()));
			}
		}
		if(dad[i]<i){
			add(dad[i]+1);
		}
		qry(1,a+1);
		for(int j=1;j<=m;j++)
		{
			dp[i][j]+=res[j-1];
			(dp[i][j]>=mod)&&(dp[i][j]-=mod);
		}
		if(b){
			qry(0,b+1);
			for(int j=1;j<=m;j++)
			{
				dp[i][j]+=res[j-1];
				(dp[i][j]>=mod)&&(dp[i][j]-=mod);
			}
			qry(0,a+1);
			for(int j=1;j<=m;j++)
			{
				dp[i][j]-=res[j-1];
				(dp[i][j]<0)&&(dp[i][j]+=mod);
			}
		}
		push(dad[i]<i,i);
	}
	for(int i=1;i<=m;i++)
	{
		printf("%d\n",dp[n][i]);
	}
}
signed main(){
	#ifdef LOCAL
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	atexit([](){fprintf(stderr,"%.3lfs\n",(double)clock()/CLOCKS_PER_SEC);});
	#endif
	solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 10060kb

input:

4 3
1 2
2 3
2 4

output:

1
2
2

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 10184kb

input:

7 7
2 5
3 6
4 5
5 1
1 6
6 7

output:

1
1
0
0
1
2
1

result:

ok 7 lines

Test #3:

score: -100
Runtime Error

input:

200000 20
1 2
1 3
1 4
6 5
6 7
6 8
12 9
12 10
12 11
13 14
13 15
13 16
20 17
20 18
20 19
21 22
21 23
21 24
21 25
1 13
6 13
12 13
20 13
21 13
27 26
27 28
27 29
32 30
32 31
32 33
34 35
34 36
34 37
38 39
38 40
38 41
43 42
43 44
43 45
46 47
46 48
46 49
46 50
27 38
32 38
34 38
43 38
46 38
51 52
51 53
51 54...

output:


result: