QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#202521#5157. High-quality Tree514imbaRE 1ms3788kbC++141.6kb2023-10-06 10:56:022023-10-06 10:56:02

Judging History

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

  • [2023-10-06 10:56:02]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3788kb
  • [2023-10-06 10:56:02]
  • 提交

answer

#include<bits/stdc++.h>
#define MAXN 200000
using namespace std;
template<typename T>
inline void read( T &n )
{
	n=0;bool w=false;char ch=getchar();
	while( ch>'9' || ch<'0' ) w=!(ch^'-'),ch=getchar();
	while( ch<='9' && ch>='0' ) n=(n<<3)+(n<<1)+(ch^48),ch=getchar();
	n=w?-n:n;
}

int n,ans;
struct Edge
{
	int to,nxt;
}edg[MAXN+5];
int head[MAXN+5],edg_num;
void add( int u , int v )
{
	++edg_num;
	edg[edg_num].to=v;
	edg[edg_num].nxt=head[u];
	head[u]=edg_num;
}

int lson[MAXN+5],rson[MAXN+5],depth[MAXN+5],size[MAXN+5];
void dfs( int u , int fa=0 )
{
	depth[u]=size[u]=1;
	for(int i=head[u];i;i=edg[i].nxt)
	{
		int v=edg[i].to;
		if( v==fa ) continue;
		if( !lson[u] ) lson[u]=v;
		else rson[u]=v;
		dfs(v,u);
		depth[u]=max(depth[lson[u]],depth[rson[u]])+1;
		size[u]=size[lson[u]]+size[rson[u]]+1;
	}
}
void rub( int u , int d )
{
	if( !u ) return;
	if( d==0 ) 
	{
		ans-=size[lson[u]]+size[rson[u]];
		lson[u]=rson[u]=0;
		depth[u]=size[u]=1;
		return;
	}
	rub(lson[u],d-1);
	rub(rson[u],d-1);
	size[u]=size[lson[u]]+size[rson[u]]+1;
	depth[u]=max(depth[lson[u]],depth[rson[u]])+1;
}
void solve( int u )
{
	if( !u ) return;
	solve(lson[u]);
	solve(rson[u]);
	if( depth[lson[u]]>depth[rson[u]] ) swap(lson[u],rson[u]);
	if( depth[rson[u]]-depth[lson[u]]>1 )
		rub(rson[u],depth[lson[u]]);
	depth[u]=max(depth[lson[u]],depth[rson[u]])+1;
	size[u]=size[lson[u]]+size[rson[u]]+1;
}

int main()
{
	read(n);
	ans=n;
	for(int i=1;i<n;i++)
	{
		int a,b;
		read(a),read(b);
		add(a,b),add(b,a);
	}
	dfs(1);
	solve(1);
	printf("%d",n-ans);
	return 0;
 } 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3764kb

input:

6
1 2
1 3
3 4
3 5
5 6

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3788kb

input:

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

output:

3

result:

ok single line: '3'

Test #3:

score: -100
Runtime Error

input:

200000
167246 158246
40931 40296
178588 27974
35171 899
4204 163250
101422 9230
55420 93371
16012 140142
28866 154497
33519 180725
50361 52348
46923 175364
126599 169575
15138 34958
164256 64770
63123 130169
154172 168301
127476 54744
199964 81879
173765 69220
178225 73653
59861 46415
138112 17507
8...

output:


result: