题解 CF620E 【New Year Tree】

MikeDuke · 2020-02-13 10:54:57 · 题解

因为红色的MikeDuke变成了橙色的MikeDuke

所以我来水题解了。。

珂学的力量是有极限的！

这题一眼珂学题，然而被毒瘤出题人卡了。。

在放出正解之前，我提供一份丑陋不堪，常数巨大的珂学代码供各位神犇参考

#include <bits/stdc++.h>

using namespace std;

#define M 1000005


inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
    while (isdigit(ch)) { (x *= 10) += ch - '0'; ch = getchar(); }
    return x * f;
}

int n, cnt, m, opt, t1, t2;

int col[M], dfn[M], siz[M], ver[M];

vector<int> G[M];

inline void add_edge(int u, int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}

struct Node
{
    int l,r;
    mutable int v;
    Node(int L, int R=-1, int V=0):l(L), r(R), v(V) {}
    bool operator<(const Node& x) const
    {
        return l < x.l;
    }
};

set<Node> s;

typedef set<Node>::iterator IT;

inline IT split(int pos)
{
    IT it = --s.upper_bound(Node(pos));
    if (it->l == pos) return it;
    int ls = it->l, rs = it->r, val = it->v;
    s.erase(it); s.insert(Node(ls, pos - 1, val));
    return s.insert(Node(pos, rs, val)).first;
}

inline void assign(int l, int r, int v)
{
    IT itr = split(r + 1), itl = split(l);
    s.erase(itl, itr);
    s.insert(Node(l, r, v));
}

void dfs(int u, int c_fa)
{
    siz[u] = 1;
    dfn[u] = ++cnt;
    ver[cnt] = u;
    int sz = G[u].size();
    for (int i = 0; i < sz; i++)
    {
        int v = G[u][i];
        if (v == c_fa) continue;
        dfs(v, u);
        siz[u] += siz[v];
    }
}

inline int query(int u)
{
    IT itr = split(dfn[u] + siz[u]), itl = split(dfn[u]);
    int cnt[65] = {}, ans = 0;
    for (IT it = itl; it != itr; it++)
    {
        if (!cnt[it->v]) ans++;
        cnt[it->v]++;
    }
    return ans;
}

int main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
    {
        col[i] = read();
    }

    for (int i = 1; i < n; i++)
    {
        add_edge(read(), read());
    }

    dfs(1, 0);

    for (int i = 1; i <= n; i++)
    {
        int p = ver[i];
        s.insert( Node(dfn[p], dfn[p], col[p]) );
    }

    for (int i = 1; i <= m; i++)
    {
        opt = read(), t1 = read();
        if (opt == 1)
        {
            t2 = read();
            assign(dfn[t1], dfn[t1] + siz[t1] - 1, t2);
        }
        if (opt == 2)
        {
            printf("%d\n", query(t1));
        }
    }

    return 0;
}

time limit exeeded on test 67..

如果能开O2我将绝杀，可惜开不得

那我们来看正解

我在读题的时候偶然发现了

1 <= c[i] <= 60

我又恰巧想到了

1 << 60 ≈ long long上限

那么这说明可以使用状态压缩

想必做这道题的神犇们都熟练掌握树链剖分

那么我们可以轻易知道对以一个点为根的子树进行奇♂怪的操作可以转化为在dfn序上，对一段连续区间进行奇♂怪的操作。

具体来说，对以u为根的子树进行操作等价在dfn序上对闭区间 (dfn[u], dfn[u] + siz[u] - 1)进行操作

dfn序列可以用线段树维护

假设dat用来存储一段区间上的颜色信息

那么可以使用如下的方法

dat的第i位是1，则dat所表示的区间就有i这种颜色

如何pushup

想必各位神犇熟练掌握位运算的各种技巧

那么就很容易得到以下式子

dat[pos] = dat[pos<<1] | dat[pos<<1|1]

左右子区间任何一个有了某种颜色，那么母区间一定也有这种颜色，所以使用位运算中的或

如何pushdown

也很容易理解

最后，完整代码

#include <bits/stdc++.h>

using namespace std;

#define M 400005

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
    while (isdigit(ch)) { (x *= 10) += ch - '0'; ch = getchar(); }
    return x * f;
}

int n, m, cnt, opt, t1, t2;
int l_[M<<2], r_[M<<2], siz[M], ver[M], dfn[M], col[M];
long long mark[M<<2], dat[M<<2];

vector<int> G[M];

inline void add_edge(int u, int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}

inline int count(long long val) // 一个状态中有多少个1，即不同的颜色数
{
    int res = 0;
    while (val)
    {
        if (val & 1) res++;
        val >>= 1;
    }
    return res;
}

inline void push_down(int pos)
{
    if (mark[pos] != 0)
    {
        mark[pos<<1] = mark[pos<<1|1] = mark[pos];
        dat[pos<<1] = dat[pos<<1|1] = mark[pos];
        mark[pos] = 0;
    }
}

void build(int pos, int l, int r)
{
    l_[pos] = l, r_[pos] = r;
    if (l == r)
    {
        dat[pos] = 1ll << col[ver[l]]; // 直接将状态中的第col位变成1，表示有这种颜色
        return;
    }
    int mid = (l + r) >> 1;
    build(pos<<1, l, mid);
    build(pos<<1|1, mid + 1, r);
    dat[pos] = dat[pos<<1] | dat[pos<<1|1];
}

void upd(int pos, int l, int r, int c)
{
    if (l_[pos] >= l && r_[pos] <= r)
    {
        mark[pos] = dat[pos] = 1ll << c;
        return;
    }
    push_down(pos);
    int mid = (l_[pos] + r_[pos]) >> 1;
    if (l <= mid) upd(pos<<1, l, r, c);
    if (r > mid) upd(pos<<1|1, l, r, c);
    dat[pos] = dat[pos<<1] | dat[pos<<1|1];
}

long long query(int pos, int l, int r)
{
    if (l_[pos] >= l && r_[pos] <= r)
    {
        return dat[pos];
    }
    long long ans = 0;
    push_down(pos);
    int mid = (l_[pos] + r_[pos]) >> 1;
    if (l <= mid) ans |= query(pos<<1, l, r);
    if (r > mid) ans |= query(pos<<1|1, l, r);
    dat[pos] = dat[pos<<1] | dat[pos<<1|1];
    return ans; // query返回的是压缩后的状态
}

void dfs(int u, int c_fa)
{
    siz[u] = 1, dfn[u] = ++cnt, ver[cnt] = u;
    int sz = G[u].size();
    for (int i = 0; i < sz; i++)
    {
        int v = G[u][i];
        if (v == c_fa) continue;
        dfs(v, u);
        siz[u] += siz[v];
    }
}

int main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
        col[i] = read();
    for (int i = 1; i < n; i++)
        add_edge(read(), read());

    dfs(1, 0);

    build(1, 1, n);

    for (int i = 1; i <= m; i++)
    {
        opt = read(), t1 = read();
        if (opt == 1)
        {
            t2 = read();
            upd(1, dfn[t1], dfn[t1] + siz[t1] - 1, t2);
        }
        else
        {
            printf("%d\n", count(query(1, dfn[t1], dfn[t1] + siz[t1] - 1)));
        }
    }
}