智障初二小朋友，4.5kb代码去A别人600b代码A的题，复杂度还被std碾压 T_T 看来我这种智障不看题解就要完

我们考虑计算每条路径上黑色节点数的最大值，我们可以参考字典树的思想，将所有叶子节点到根节点路径上的点的 cnt + 1, 这样，最后那些 cnt 为 1 的点一定只会对一个叶子节点到根节点上的黑点数量产生影响 (dfs一遍不难实现) 知道了这一点的话，我们考虑如果在一个 cnt 不为 1 的点染色，那么一定会有多个点一起增加，所以我们只要找到到根 cnt 为 1 的点数量最少的叶子节点，将它到根节点的长度作为 Min, 再将 Min 对所有点到根的长度取min (保证合法性)

现在我们只需贪心地染色即可，由于染色的点越高，它就越能满足更多的点，所以我们贪心的染路径上最下面 Min 个点 具体细节是，为了避免非法情况，我们按照深度从小到大的顺序处理叶子节点，对于每个点先减去它到根已经染好的数量，再染剩下的 怎么维护？好问题，LCT? LCT! 4.5kb代码就是这么出来的 T_T 我们只需维护树上路径和，支持覆盖操作即可，找下面第 Min 个点可以直接找 Splay 中第 Min 大

复杂度 $O(Nlog_2N)$

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define print(...) printf(__VA_ARGS__), fflush(stdout)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

inline int read()
{
    register int c = getchar(), sum(0), fg(1);
    while (c < '0' || c > '9') { if (c == '-') fg = -1; c = getchar(); }
    while (c >= '0' && c <= '9') sum = sum * 10 + c - '0', c = getchar();
    return sum * fg;
}

const int oo = 0x3f3f3f3f;

const int maxn = 100000, maxl = 20;

struct edge
{
    int id, nxt;

    edge(const int &_id = 0, const int &_nxt = 0): id(_id), nxt(_nxt) { }
};

edge e[(maxn << 1) + 5];

int st[maxn + 5], Count[maxn + 5], cnt;

inline void add(const int &x, const int &y, const int &type = 1)
{
    ++Count[y];
    e[cnt] = edge(y, st[x]), st[x] = cnt++;
    if (type) add(y, x, 0);
}

int Size;

struct LCT
{
    int ch[maxn + 5][2], pre[maxn + 5], rev[maxn + 5], size[maxn + 5], val[maxn + 5], sum[maxn + 5], Set[maxn + 5];

#define L ch][0
#define R ch][1

    inline bool is_root(const int &x) { return x[pre][L] != x && x[pre][R] != x; }

    inline void push_up(const int &x)
    {
        x[size] = 1 + x[L][size] + x[R][size];
        x[sum] = x[val] + x[L][sum] + x[R][sum];
    }

    inline void push_down(const int &x)
    {
        if (~x[Set])
        {
            if (x[L]) x[L][val] = x[Set], x[L][Set] = x[Set], x[L][sum] = x[Set] * x[L][size];
            if (x[R]) x[R][val] = x[Set], x[R][Set] = x[Set], x[R][sum] = x[Set] * x[R][size];
            x[Set] = -1;
        }
        if (x[rev])
        {
            if (x[L]) x[L][rev] ^= 1;
            if (x[R]) x[R][rev] ^= 1;
            swap(x[L], x[R]);
            x[rev] = 0;
        }
    }

    inline void rotate(const int x)
    {
        const int y = x[pre], T = x == y[R];
        y[ch][T] = x[ch][!T];
        if (x[ch][!T]) x[ch][!T][pre] = y;
        x[pre] = y[pre];
        if (y == y[pre][L]) y[pre][L] = x;
        if (y == y[pre][R]) y[pre][R] = x;
        x[ch][!T] = y, y[pre] = x;
        push_up(y);
    }

    inline void push(const int &x)
    {
        if (!is_root(x)) push(x[pre]);
        push_down(x);
    }

    inline void splay(const int &x)
    {
        push(x);
        while (!is_root(x))
        {
            int y = x[pre], z = y[pre];
            if (!is_root(y)) rotate((x == y[L]) ^ (y == z[L]) ? x : y);
            rotate(x);
        }
        push_up(x);
    }

    inline int access(const int &x)
    {
        for (splay(x), x[R] = 0, push_up(x); x[pre]; splay(x))
        {
            splay(x[pre]);
            x[pre][R] = x;
            push_up(x[pre]);
        }
        return x;
    }

    inline void change_root(const int &x)
    {
        access(x)[rev] ^= 1;
    }

    inline void link(const int &x, const int &y)
    {
        access(y);
        y[pre] = x;
        access(y);
    }

    inline int locate(const int &x, const int &k)
    {
        if (k == x[R][size] + 1) return x;
        if (k <= x[R][size]) return locate(x[R], k);
        else return locate(x[L], k - x[R][size] - 1);
    }

    inline int query(const int &x)
    {
        access(x);
        int ans = x[sum], y = locate(x, Size - ans);
        change_root(x);
        access(y);
        y[Set] = 1, y[val] = 1, y[sum] = y[size];
        change_root(1);
        return ans;
    }
}t;

int leaf[maxn + 5], sum[maxn + 5], dis[maxn + 5];

inline void build(const int &x, const int &fa)
{
    if (x != 1 && Count[x] == 1)
    {
        sum[x] = 1;
        return;
    }
    for (int i = st[x]; ~i; i = e[i].nxt)
    {
        int y = e[i].id;
        if (y != fa)
        {
            t.link(x, y);
            build(y, x);
            sum[x] += sum[y];
        }
    }
}

int min_id[maxn + 5];

inline int dfs(const int &x, const int &fa)
{
    if (x != 1 && Count[x] == 1)
    {
        min_id[x] = x;
        return 1;
    }
    int Min = oo; min_id[x] = 0;
    for (int i = st[x]; ~i; i = e[i].nxt)
    {
        int y = e[i].id;
        if (y != fa)
        {
            dis[y] = dis[x] + 1;
            chkmin(Min, dfs(y, x)) ? min_id[x] = min_id[y] : 0;
        }
    }
    return Min + (sum[x] == 1);
}

int N, M;

struct Leaf
{
    int x, y;

    inline bool operator < (const Leaf &obj) const { return y < obj.y; }

    Leaf(const int &_x = 0, const int &_y = 0): x(_x), y(_y) { }
}T[maxn +5];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
#endif
    memset(st, -1, sizeof st), cnt = 0;
    N = read();
    if (N == 1)
    {
        puts("1");
        return 0;
    }
    REP(i, 1, N) t.size[i] = 1, t.val[i] = 0, t.Set[i] = -1;
    REP(i, 2, N)
    {
        int x = read(), y = read();
        add(x, y);
    }
    M = 0;
    build(1, 0);
    dis[1] = 1, dfs(1, 0);
    Size = dis[min_id[1]];
    REP(i, 2, N)
        if (Count[i] == 1)
            T[++M] = Leaf(i, dis[i]);
    sort(T + 1, T + M + 1);
    REP(i, 1, M) leaf[i] = T[i].x;
    REP(i, 1, M) chkmin(Size, dis[leaf[i]]);
    int ans = 0;
    REP(i, 1, M) ans += Size - t.query(leaf[i]);
    printf("%d\n", ans);
    return 0;
}

作为一名OI选手初二小朋友，我还是觉得静态的LCT好写，于是推翻了以前幼稚的代码虽然以前的动态版本也放在下面了，大爷们勿喷 静态:

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (register int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

inline int read()
{
    int c = getchar(), fg = 1, sum = 0;
    while (c < '0' || c > '9') { if (c == '-') fg = -1; c = getchar(); }
    while (c >= '0' && c <= '9') sum = sum * 10 + c - '0', c = getchar();
    return sum * fg;
}

const int maxn = 300000, oo = 0x3f3f3f3f;

int N, M;

struct LCT
{
#define L ch][0
#define R ch][1

    int val[maxn + 5], Max[maxn + 5], add[maxn + 5], rev[maxn + 5];

    int ch[maxn + 5][2], pre[maxn + 5];

    inline bool is_root(const int &x) { return x != x[pre][L] && x != x[pre][R]; }

    void init(const int *value)
    {
        REP(i, 0, N ? N : maxn)
        {
            i[val] = i[Max] = i[value];
            i[rev] = i[add] = i[pre] = i[L] = i[R] = 0;
        }
        0[val] = 0[Max] = -oo;
    }

    inline void push_up(const int &x)
    {
        x[Max] = x[val];
        if (x[L]) chkmax(x[Max], x[L][Max]);
        if (x[R]) chkmax(x[Max], x[R][Max]);
    }

    inline void push_down(const int &x)
    {
        if (x[add])
        {
            if (x[L]) x[L][val] += x[add], x[L][Max] += x[add], x[L][add] += x[add];
            if (x[R]) x[R][val] += x[add], x[R][Max] += x[add], x[R][add] += x[add];
            x[add] = 0;
        }
        if (x[rev])
        {
            swap(x[L], x[R]);
            if (x[L]) x[L][rev] ^= 1;
            if (x[R]) x[R][rev] ^= 1;
            x[rev] = 0;
        }
    }

    inline void rotate(const int &x)
    {
        register int y = x[pre], T = x == y[R];
        x[ch][!T][pre] = y;
        y[ch][T] = x[ch][!T];
        x[pre] = y[pre];
        if (y == y[pre][L]) y[pre][L] = x;
        else if (y == y[pre][R]) y[pre][R] = x;
        y[pre] = x;
        x[ch][!T] = y;
        push_up(y), push_up(x);
    }

    inline void push_tag(int x)
    {
        static int stack[maxn + 5], top; top = 0;
        while (!is_root(x)) stack[top++] = x, x = x[pre];
        push_down(x);
        while (top) push_down(stack[--top]);
    }

    inline void splay(int x)
    {
        push_tag(x);
        while (!is_root(x))
        {
            int y = x[pre], z = y[pre];
            if (is_root(y)) rotate(x);
            else if ((z[L] == y) == (y[L] == x))
                rotate(y), rotate(x);
            else rotate(x), rotate(x);
        }
        push_up(x);
    }

    inline int access(int x)
    {
        int y = 0;
        while (x)
        {
            splay(x);
            x[R] = y;
            push_up(x);
            y = x;
            x = x[pre];
        }
        return y;
    }

    inline void change_root(const int &x)
    {
        access(x)[rev] ^= 1;
        splay(x);
    }

    inline int get_root(int x)
    {
        access(x);
        splay(x);
        while (x[L]) x = x[L];
        splay(x);
        return x;
    }

    inline void link(const int &x, const int &y)
    {
        change_root(x);
        x[pre] = y;
        access(x);
    }

    inline void cut(const int &x, const int &y)
    {
        change_root(x);
        access(y), splay(y);
        y[L] = y[L][pre] = 0;
        push_up(y);
    }

    inline void update(int x, int y, int w)
    {
        change_root(x);
        y = get_root(y);
        y[Max] += w, y[val] += w, y[add] += w;
    }

    inline int query(int x, int y)
    {
        change_root(x);
        y = get_root(y);
        return y[Max];
    }

    inline bool p(int x, int y)
    {
        while (x[pre]) x = x[pre];
        while (y[pre]) y = y[pre];
        return x == y;
    }
};

int main()
{
#ifndef ONLINE_JUDGE
 freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
 return 0;
}

动态:

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define DREP(i, a, b) for (int i = (a), i##_start_ = (b); i >= i##_start_; --i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b){ return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b){ return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int dmax = 300100, oo = 0x3f3f3f3f;

int n, m;

struct node
{
    node *f, *ch[2];
    int val, max, rev, add;
}c[dmax], *cur, *Null;

#define L ch[0]
#define R ch[1]

node *new_node(int k)
{
    cur->val = cur->max = k;
    cur->rev = cur->add = 0;
    cur->f = cur->L = cur->R = Null;
    return cur++;
}

void init()
{
    Null = c;
    Null->f = Null->L = Null->R = Null;
    Null->val = Null->max = -oo;
    Null->rev = Null->add = 0;
    cur = c + 1;
}

struct lct
{
    inline bool is_root(node *t) { return t == Null || t->f->L != t && t->f->R != t; }
    inline void push_up(node *t) { t->max = max(t->val, max(t->L->max, t->R->max)); }
    inline void push_down(node *t)
    {
        if (t->rev)
        {
            if (t->L != Null) t->L->rev ^= 1;
            if (t->R != Null) t->R->rev ^= 1;
            t->rev = 0;
            swap(t->L, t->R);
        }
        if (t->add)
        {
            if (t->L != Null) t->L->val += t->add, t->L->max += t->add, t->L->add += t->add;
            if (t->R != Null) t->R->val += t->add, t->R->max += t->add, t->R->add += t->add;
            t->add = 0;
        }
    }
    inline void rotate(node *x)
    {
        if (is_root(x)) return;
        node *y = x->f;
        int k = x == y->R;
        x->f = y->f;
        y->ch[k] = x->ch[!k];
        if (x->ch[!k] != Null) x->ch[!k]->f = y;
        if (!is_root(y))
        {
            if (y == y->f->L)
                y->f->L = x;
            else y->f->R = x;
        }
        x->ch[!k] = y;
        y->f = x;
        push_up(y);
    }
    void splay(node *x)
    {
        static node *S[dmax];
        int top = 1;
        S[0] = x;
        for (node *Cur = x; !is_root(Cur); Cur = Cur->f)
            S[top++] = Cur->f;
        while (top > 0) push_down(S[--top]);
        while (!is_root(x))
        {
            node *y = x->f;
            if (!is_root(y))
                rotate(x);
            else{
                if (x == y->f->L->L || x == y->f->R->R)
                    rotate(y);
                else rotate(x);
                rotate(x);
            }
        }
        push_up(x);
    }
    node *access(node *x)
    {
        node *y = Null;
        while (x != Null)
        {
            splay(x);
            x->R = y;
            y->f = x;
            push_up(x);
            y = x;
            x = x->f;
        }
        return y;
    }
    inline void change_root(node *x) { access(x)->rev ^= 1; splay(x); }
    inline void link(node *x, node *y)
    {
        change_root(x);
        x->f = y;
        access(x);
    }
    inline void cut(node *x)
    {
        access(x);
        splay(x);
        x->L = x->L->f = Null;
        push_up(x);
    }
    node *get_root(node *x)
    {
        access(x);
        splay(x);
        while (x->L != Null) x = x->L;
        splay(x);
        return x;
    }
    bool p(node *x, node *y)
    {
        while (x->f != Null) x = x->f;
        while (y->f != Null) y = y->f;
        return x == y;
    }
}t;

int main()
{
#ifndef ONLINE_JUDGE
     freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
#endif
    return 0;
}

如题没错，现在的年轻选手越来越厉害了 比如我认识一个小朋友叫罗恺 @cnyali_lk 的，他才初一就会树链剖分了，我们都是他的忠实粉丝，他初一就得了提高组一等奖，现在正致力于初一进省队，拿NOI Au，让我们为小朋友加油