显然判断每个点只需要判断子树是否小于等于n/2即可

那么我们虚拟一个根，然后计算每个子树的size，而这个点的子树的size和n-这个点的size就是我们需要找的

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << #x << " = " << x << endl#define printarr2(a, b, c) for1(i, 1, b) { for1(j, 1, c) cout << a[i][j]; cout << endl; }#define printarr1(a, b) for1(i, 1, b) cout << a[i]; cout << endlinline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a
            
             >1)) mark[x]=1;}int main() { read(n); for1(i, 1, n-1) add(getint(), getint()); dfs((n+1)>>1); for1(i, 1, n) if(mark[i]) printf("%d\n", i); return 0;}
            
           
          
         
        
       
      
     

 

 

---

 

 

Description

    约翰意识到贝茜建设网络花费了他巨额的经费，就把她解雇了．贝茜很愤怒，打算狠狠报

复．她打算破坏刚建成的约翰的网络．    约翰的网络是树形的，连接着 N(1≤N≤10000)个牛棚．她打算切断某一个牛棚的电源，使和这个牛棚相连的所有电缆全部中断．之后，就会存在若干子网络．为保证破坏够大，每一个 子网的牛棚数不得超过总牛棚数的一半,那哪些牛棚值得破坏呢？

Input

    第1行：一个整数N.

    第2到N+1行：每行输入两个整数，表示一条电缆的两个端点．

Output

    按从小到大的顺序，输出所有值得破坏的牛棚．如果没有一个值得破坏，就输出“NONE”．

Sample Input

10

1 2

2 3

3 4

4 5

6 7

7 8

8 9

9 10

3 8

Sample Output

3

8

如果牛棚3或牛棚8被破坏，剩下的三个子网节点数将是5，2，2，没有超过5的．

来源信息

HINT

Source