A simple Blog for wyx I've been down the bottle hoping.
POJ Tree cut
发表于: | 分类: Oi | 评论:0 | 阅读:179

这是一道非常经典的题目
就是类似求树的重心一样的题目,所以 你们自己脑补一下就好>_<
算了我还是简单的说一下吧
就是$f[x]$表示$x$去掉$x$能达到的最大值
我们维护一个$size$,然后每次取一下$MAX$就行了
$$f[x] = max(size[son[x]],n-size[x])$$
别忘了输出$NONE$

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define N 10000+5
#define M 20000+5
using namespace std;

int head[N];
int size[N];

inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
} 

struct graph
{
    int next,to;
    graph () {}
    graph (int _next,int _to)
    :next(_next),to(_to){}
}edge[M];

inline void add(int x,int y)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y);
    head[x] = cnt;
    edge[++cnt] = graph(head[y],x);
    head[y] = cnt;
}

int f[N],n;

void DFS(int x,int fa)
{
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to!=fa)
            DFS(edge[i].to,x),size[x]+=size[edge[i].to];
    f[x] = n - size[x] - 1;
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to!=fa)
            f[x] = max(f[x],size[edge[i].to]);
    size[x]++;
}

int main()
{
    n = read();
    for(int i=1;i<n;++i)
    {
        int x = read(),y = read();
        add(x,y);
    }
    DFS(1,1);
    bool flag = false;
    for(int i=1;i<=n;++i)
        if(f[i]*2<=n)
            printf("%d\n",i),flag = true;
    if(!flag)
        puts("NONE");
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP