2020牛客夏季多校訓練キャンプ(第2回)Cカバーthe Tree

21735 ワード

リーフノードがL個であると仮定する.まず下界がL+1 2frac{L+1}{2}2 L+1であることを証明できる.まず葉ノードを抽出し、dfsシーケンスでソートします.[1,L][1,L][1,L]と表記して[i,i+L 2](i,<=L 2)[i,i+frac{ L}{2}](i<=frac{ L}{2})[i,i,+2 L](i<=2 L)を接続するサブツリーがあると仮定し,その葉ノード番号は[l,r][l,r][l,r][l,r]であり,rL/2 l>L/2 l>L/2と仮定すると,サブツリーからルートノードへの鎖は[r−L 2,r][r−frac{L}{2},r][r−2 L,r]で遍歴されるに違いない.lL/2 r>L/2 r>L/2 r>L/2同理を仮定しても遍歴される.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
#include
#include 
#pragma GCC optimize(2)
#define up(i,a,b)  for(int i=a;i
#define dw(i,a,b)  for(int i=a;i>b;i--)
#define upd(i,a,b) for(int i=a;i<=b;i++)
#define dwd(i,a,b) for(int i=a;i>=b;i--)
//#define local
typedef long long ll;
typedef unsigned long long ull;
const double esp = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
ll read()
{
    char ch = getchar(); ll x = 0, f = 1;
    while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
typedef pair<int, int> pir;
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lrt root<<1
#define rrt root<<1|1
const int N = 2e5 + 10;
int n;
struct node {
    int next, to;
}edge[N << 1];
int head[N];
int cnt;
void addedge(int u, int v)
{
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
int deg[N];
int dfn[N]; int st;
void dfs(int u, int fa)
{
    dfn[u] = ++st;
    for (int i = head[u]; ~i; i = edge[i].next)
    {
        int v = edge[i].to;
        if (v == fa)continue;
        dfs(v, u);
    }
}
bool cmp(int a, int b)
{
    return dfn[a] < dfn[b];
}
int main()
{
    memset(head, -1, sizeof(head));
    n = read();
    int u, v;
    upd(i, 1, n - 1)
    {
        u = read(), v = read();
        addedge(u, v);
        addedge(v, u);
        deg[u]++;
        deg[v]++;
    }
    if (n == 1)
    {
        printf("0
"); return 0;
    }
    int root = 1;
    int num = 0;
    vector<int>vec;
    upd(i, 1, n)
    {
        if (deg[i] != 1)
        {
            root = i;
        }
        else vec.push_back(i),num++;
    }
    printf("%d
", (num + 1) / 2);
    dfs(root, 0);
    sort(vec.begin(), vec.end(), cmp);
    int mid = vec.size() / 2;
    up(i, 0, mid)
    {
        printf("%d %d
", vec[i], vec[i + mid]);
    }
    if (num & 1)
        printf("%d %d
", vec.back(), root);
    return 0;
}

Poj 3159(差分制約システム、SPFA+スタック、Dij+heap)

【angular】FormBuilderの使い方