只能考虑性质了。

把最后选择的k个点的连通块求出来，连通块内部的点表示都是互异的

连通块外部的点只能形成若干条链，并且这k个点的每一个最多与一个外部点相连。

直接从每个叶子往上跳，当fa[x]度数>2的时停下

如果fa[x]之前没有链，那么可以先省下一次，否则就要把x变成k个点之一

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
      
       using namespace std;typedef long long ll;template
       
        il void rd(T &x){    char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}template
        
         il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Modulo{const int mod=998244353;int ad(int x,int y){ return (x+y)>=mod?x+y-mod:x+y;}void inc(int &x,int y){x=ad(x,y);}int mul(int x,int y){ return (ll)x*y%mod;}void inc2(int &x,int y){x=mul(x,y);}int qm(int x,int y=mod-2){ int ret=1;while(y){ if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}}//using namespace Modulo;namespace Miracle{const int N=1e5+5;int du[N],n;vector
           
            to[N];int fa[N],ans;bool vis[N],has[N];void dfs(int x){ for(solid y:to[x]){ if(y==fa[x]) continue; fa[y]=x; dfs(y); }}int main(){ rd(n);int x,y; int rt=0; for(reg i=1;i
            
             2) rt=x; if(du[y]>2) rt=y; } if(!rt) printf("1"); else{ dfs(rt); for(reg i=1;i<=n;++i){ if(du[i]==1){ // cout<<" ii "<
             <