QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#202521 | #5157. High-quality Tree | 514imba | RE | 1ms | 3788kb | C++14 | 1.6kb | 2023-10-06 10:56:02 | 2023-10-06 10:56:02 |
Judging History
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;
}
详细
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...