第一道场上自己做出来的E题...虽然是div3，而且是原题...
当时做完ABC，D题没有思路就去怼E了，然后发现貌似原题？
事实上就是原题...
给个原题链接...
第二个我还写过题解...题解链接
其实就是一个贪心，首先深度在2以内的就不用管它了
对于深度大于2的点，我们显然只能拉一条边在他那里或者他的父亲那里，同样的，显然我们把那条边放在他父亲那里更划算，因为可以到达更多的点
所以一遍dfs处理出深度，然后按深度放入大根堆里面，每次取出一个点，对它的父亲的周围节点染色，遇到被染色过的直接continue掉就好
然后我当时没有给该节点的祖父染色...事实上是要染的...然后就WA8了5次，罚时爆炸...
复杂度$O(nlogn)$
#include <bits/stdc++.h>
#define ll long long
#define inf 1<<30
#define il inline
#define in1(a) read(a)
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,b,c,d) in2(a,b),in2(c,d)
il void readl(ll &x){
x=;ll f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-f;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
x*=f;
}
il void read(int &x){
x=;int f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-f;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
x*=f;
}
using namespace std;
/*===================Header Template=====================*/
#define N 1000010
int n,head[N],cnt;
struct edge{
int to,nxt;
}e[N];
struct node {
int id,dep,fa;
bool operator < (const node &x)const {
return x.dep>dep;
}
}a[N];
void ins(int u,int v){
e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
e[++cnt].to=u;e[cnt].nxt=head[v];head[v]=cnt;
}
void dfs(int x,int f,int dep){
a[x].fa=f;
a[x].id=x;
a[x].dep=dep;
for(int i=head[x];i;i=e[i].nxt){
if(e[i].to==f)continue;
dfs(e[i].to,x,dep+);
}
}
bool vis[N];
priority_queue<node>q;
int main(){
in1(n);
for(int i=;i<n;i++){
int x,y;
in2(x,y);
ins(x,y);
}
dfs(,,);
for(int i=;i<=n;i++){
if(a[i].dep>)q.push(a[i]);
else vis[i]=;
}
int ans=;
while(!q.empty()){
node t=q.top();q.pop();
if(vis[t.id])continue;
ans++;
int f=t.fa;
vis[t.id]=vis[f]=;
for(int i=head[f];i;i=e[i].nxt){
vis[e[i].to]=;
}
}
printf("%d\n",ans);
return ;
}