问题等价于每个三角形里至少选择两个点。

考虑拓扑，每次取出度数为$2$的点$x$，代表一个只与最多一个三角形相邻的三角形$(x,y,z)$。

如果$x$已选，那么$(x,y)$以及$(x,z)$都已经被覆盖，无需再选其它点。

否则因为至少要选两个点，选$y$和$z$一定最优。

时间复杂度$O(n)$。

 

#include
     
      const int N=100010;int n,i,x,y,z,d[N],g[N],v[N<<2],nxt[N<<2],ed,vis[N],h,t,q[N],ans,f[N];inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}inline void add(int x,int y){d[x]++;v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}int main(){  read(n);  for(i=1;i<=n+n-3;i++)read(x),read(y),add(x,y),add(y,x);  for(h=i=1;i<=n;i++)if(d[i]==2)q[++t]=i;  while(h<=t){    x=q[h++];    if(d[x]!=2)continue;    vis[x]=1,y=0;    for(i=g[x];i;i=nxt[i])if(!vis[v[i]]){      if(y)z=v[i];else y=v[i];      if((--d[v[i]])==2)q[++t]=v[i];    }    if(!f[x])f[y]=f[z]=1;  }  for(i=1;i<=n;i++)ans+=f[i];  return printf("%d",ans),0;}