UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#208409#3792. Water and Icemygr100311ms11836kbC++2.5kb2024-08-02 12:39:272024-08-02 12:58:14

answer

#include<bits/stdc++.h>
using namespace std;
const int Max=4e5+5;
class so1{
public:
	struct edge{
		int to,next;
	}p[Max*2];
	int head[Max],last[Max],idx;
	
	void add(int u,int v)
	{
		if(!head[u])
			head[u]=++idx;
		else
			p[last[u]].next=++idx;
		last[u]=idx;
		p[idx].to=v;
	}
	int n,d;
	
	int ans[Max],cnt,fin,fans[Max];
	bool check(int now,int from,int dep)
	{
		if(from!=now and ans[now])
			return 1;
		if(dep==d-1)
			return 0;
		for(int i=head[now];p[i].to;i=p[i].next)
		{
			if(p[i].to==from)
				continue;
			if(check(p[i].to,now,dep+1))
				return 1;
		}
		return 0;
	}
	void dfs(int dep)
	{
		if(dep>n)
		{
			if(cnt<=fin)
				return ;
			for(int i=1;i<=n;i++)
				if(ans[i] and check(i,i,0))
					return ;
			fin=max(fin,cnt);
			for(int i=1;i<=n;i++)
				fans[i]=ans[i];
			return ;
		}
		ans[dep]=1;
		cnt++;
		dfs(dep+1);
		ans[dep]=0;
		cnt--;
		dfs(dep+1);
	}
	void solve()
	{
		
		int u,v;
		for(int i=1;i<n;i++)
		{
			scanf("%d%d",&u,&v);
			add(u,v);add(v,u);
		}
		dfs(1);
		printf("%d\n",fin);
		for(int i=1;i<=n;i++)
			if(fans[i])
				printf("%d ",i);
	}
}s1;
class so2{
public:
	struct edge{
		int to,next;
	}p[Max*2];
	int head[Max],last[Max],idx=0;
	void add(int u,int v)
	{
		if(!head[u])
			head[u]=++idx;
		else
			p[last[u]].next=++idx;
		last[u]=idx;
		p[idx].to=v;
	}
	int dep[Max],fa[Max],f[Max];
	int vis[Max];
	void dfs(int now,int from)
	{
		dep[now]=dep[from]+1;
		fa[now]=from;
		for(int i=head[now];p[i].to;i=p[i].next)
		{
			if(p[i].to==from)
				continue;
			dfs(p[i].to,now);
		}
	}
	int n,d;
	void paint(int now,int dep)
	{
		for(int i=1;i<=d;i++,now=fa[now])
			f[now]=max(f[now],d-i+1);
	}
	bool check(int now)
	{
		int nt=now;
		for(int i=1;i<=d;i++,nt=fa[nt])
			if(f[nt]>=i)
			{
				for(int j=1;now!=nt;j++,now=fa[now])
					f[now]=max(f[now],f[nt]-(dep[now]-dep[nt]));
				return 0;
			}
		return 1;
	}
	pair<int,int> e[Max];
	int ans[Max],cnt=0;
	void solve()
	{
	
		int u,v;
		for(int i=1;i<n;i++)
		{
			scanf("%d%d",&u,&v);
			add(u,v);add(v,u);
		}
		dfs(1,1);
		for(int i=1;i<=n;i++)
			e[i]=make_pair(dep[i],i);
		sort(e+1,e+1+n);
		for(int i=n;i>=1;i--)
		{
			if(check(e[i].second))
			{
				ans[++cnt]=e[i].second;
				paint(e[i].second,d);
			}
		}
		printf("%d\n",cnt);
		for(int i=1;i<=cnt;i++)
			printf("%d ",ans[i]);
	}
}s2;

int n,d;
int main()
{
	scanf("%d%d",&n,&d);
	if(n<=20)
	{
		s1.n=n;s1.d=d;
		s1.solve();
	}
	else
	{
		s2.n=n;s2.d=d;
		s2.solve();
	}
	
}




详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 4352kb

input:

10 5
3 7
7 10
7 8
9 1
5 4
3 9
7 5
3 2
7 6

output:

2
1 4 

result:

ok ok accepted

Test #2:

score: 10
Accepted
time: 0ms
memory: 4352kb

input:

10 4
8 5
8 6
1 8
4 9
5 3
7 10
8 4
7 2
1 7

output:

3
2 3 9 

result:

ok ok accepted

Test #3:

score: 10
Accepted
time: 0ms
memory: 4352kb

input:

10 3
7 8
1 10
4 3
1 5
1 7
2 9
1 4
7 2
2 6

output:

4
3 5 6 8 

result:

ok ok accepted

Test #4:

score: 10
Accepted
time: 0ms
memory: 4464kb

input:

3000 4
609 550
550 37
550 460
460 2476
2476 822
460 18
822 740
609 1212
822 2274
740 2276
2276 187
4...

output:

778
2803 2146 6 205 2371 2109 1212 869 1284 18 1031 1226 883 2694 1020 1651 45 573 38 2376 2333 747 ...

result:

ok ok accepted

Test #5:

score: 10
Accepted
time: 3ms
memory: 4456kb

input:

3000 10
29 699
699 832
29 2332
29 1385
699 1783
832 734
1385 1639
734 2853
29 2689
2853 2190
699 558...

output:

220
1728 539 1696 884 271 62 1893 1561 433 2000 2795 2906 1708 2637 152 2698 1630 1504 2904 2437 167...

result:

ok ok accepted

Test #6:

score: 10
Accepted
time: 0ms
memory: 4456kb

input:

3000 50
444 813
444 135
813 2265
135 2309
135 914
914 535
135 2055
2055 1225
914 2499
2055 1364
2499...

output:

20
2137 824 2544 1275 1427 2538 2634 20 2893 90 2199 2553 2395 2556 2973 789 2900 2793 667 208 

result:

ok ok accepted

Test #7:

score: 10
Accepted
time: 88ms
memory: 11836kb

input:

200000 217
31004 146202
108924 82624
43788 48134
199877 157947
92879 87010
198989 49945
175154 66735...

output:

924
67456 35624 127539 92910 73540 25439 184428 85006 130464 13791 155457 172171 61710 164999 80784 ...

result:

ok ok accepted

Test #8:

score: 10
Accepted
time: 92ms
memory: 11452kb

input:

200000 475
77454 87171
23492 138432
137402 34171
181862 18661
57910 51505
135417 198061
164845 19388...

output:

394
60394 57846 64389 50025 12771 33384 115452 176700 7839 915 182340 110299 128738 10851 62139 1713...

result:

ok ok accepted

Test #9:

score: 10
Accepted
time: 48ms
memory: 11768kb

input:

199999 4
1 2
2 3
1 4
4 5
1 6
6 7
1 8
8 9
1 10
10 11
1 12
12 13
1 14
14 15
1 16
16 17
1 18
18 19
1 20...

output:

99999
199999 199997 199995 199993 199991 199989 199987 199985 199983 199981 199979 199977 199975 199...

result:

ok ok accepted

Test #10:

score: 10
Accepted
time: 80ms
memory: 11376kb

input:

199397 946
29518 79973
29518 71183
71183 194147
29518 156561
156561 196558
196558 25260
29518 198870...

output:

159
156440 134941 66823 173468 85215 105244 123376 168267 169990 112932 174647 117477 163036 32323 3...

result:

ok ok accepted