今天做题随手翻了下提交记录
结果看到个离谱的
#include<stdio.h>
#include<vector>
#define int long long
#define k
const int N=400000+10;
int k k k k k k k n,T;std::
vector k < k k k k int> k k g[ k k k N];
int f[N], k k k k k k k k k sz[ k k N];
int find(int x){
k k k k k k k if( k k k k k k k k f[x]==x) return x;
return f[x]= k k k k k k find( k k k f k k k k k [x]); k
}
void slove(){
scanf("%lld",&n);
for(int k k k k k k i= k 1; k k k k i<= k k k k n;i++)
g[i] k k . k k k k k clear();
k k int k k k k k k k u, k v;
for(int i=1;i<=n-1;i++){
scanf k k k k k k k ("%lld%lld",&u,&v); k k k
k k k k k k k g[u].push_back(v); k k k k k k
g[v].push_back(u);
} k k k
for(int i= k k k k k k k k k k k k k 1; k i<=n;i++){
f[i]=i;
sz[i]=1;
}
int k k k k k k k k k k ans= k 0; k k k
for(int i=1;i<=n;i++){
int p=0; k k k k k k k k k k k k k k k k k k k k k k
k for k ( k int v:g[i]){
if(v>i) continue;
k k k k k k k k k k k k int a=find(v);
k k int k k k k k k k k k k b=find(i);
if(a!=b){
f[a]=b; k k k k k
k k if(sz[a]>0) k p k k k k k ++; k k k k k
sz[ k k k b]+= k k k k k k k sz[a];
} k k k k k k
k }
if(p>=2){
ans++;
sz[find(i)]-=3;
}
}
printf("%lld\n",ans);
return;
} k k k k k k k k k k k k k k
signed main(){
scanf("%lld",& k T);
while(T--){ k k
k k k k k slove(); k
}
return 0;
k }
k k k
k
这是什么玩意