题解：P14623 [2018 KAIST RUN Fall] Coloring Roads

· · 题解

真的是一道挺好玩的题，而且写的解也比较优（赛时运行时长第四快）。所以来写一写题解，权当是为明天的 NOIP 再鼓舞一下士气。

虽然赛后看了别人代码才发现自己的写法是有够猎奇的。

考虑怎么以一种非常暴力但在时间复杂度方面又有所保证的方法完成题目给出的任务。不难发现，由于每次操作针对的都是根到某个叶节点的一条路径，那么显然可以用树链剖分来把树剖分成若干条链，这样就只需要处理链上的情况了。

对于一条链，可以用一个 set 来描述其染色状态。具体来说，按深度升序存储被修改的颜色的下端点，按照链头的深度即可快速计算出每一个颜色段的长度。

每次操作暴力跳链维护即可。每次最多跳 O(\log n) 条链，在每条链上的 set 插入一个节点并删除若干个节点，最坏情况下进行 O(\log n) 次。每个插入的节点最多被后续操作删除一次，故总时间复杂度为 O(n\log^2 n)。

同时，由于除一开始的第一条链之外，所有链都会被直接清空，那么在非第一条链之外仅遍历 set 而非执行 erase 就可以做到接近 O(n\log n)。

事实上，如果你真的读完了上面的解法，你就会发现我愚不可及。上面的操作可以直接使用栈进行维护，做到严格的 O(n\log n)。代码还是别参考了，毕竟用的 set，最好自己用栈再实现一遍。

// #define Redshift_Debug
#ifdef Redshift_Debug
#define debug(...) fprintf(stderr, __VA_ARGS__)
#include <chrono>
#else
#define debug(...)
#endif
#include <iostream>
#include <set>
#include <string>
#include <utility>
using namespace std;
const int N = 2e5 + 10;
int n, c, q, tp[N], sz[N], f[N], ds[N], dep[N], cnt[N], cur[N];
basic_string<int> road[N];
using pii = pair<int, int>;
set<pii> buc[N];
void dfs1(int x)
{
    sz[x] = 1;
    for (auto &i : road[x])
    {
        if (i == f[x])
            continue;
        f[i] = x;
        dep[i] = dep[x] + 1;
        dfs1(i);
        sz[x] += sz[i];
        if (sz[ds[x]] < sz[i])
            ds[x] = i;
    }
}
void dfs2(int x)
{
    if (!ds[x])
        return;
    tp[ds[x]] = tp[x];
    dfs2(ds[x]);
    for (auto &i : road[x])
    {
        if (i == f[x] or i == ds[x])
            continue;
        tp[i] = i;
        dfs2(i);
    }
}
void run()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin >> n >> c >> q;
    cnt[0] = c;
    for (int i = 1, x, y; i < n; i++)
    {
        cin >> x >> y;
        road[x] += y;
        road[y] += x;
    }
    dfs1(1);
    tp[1] = 1;
    dfs2(1);
    for (int i = 1, x, y, z, ctp, prv; i <= q; i++)
    {
        cin >> x >> y >> z;
        cnt[cur[y]]--;
        cur[y] += dep[x];
        cnt[cur[y]]++;
        while (x)
        {
            ctp = tp[x];
            prv = dep[tp[x]] - (tp[x] != 1);
            while (buc[ctp].size() and buc[ctp].begin()->first <= dep[x])
            {
                cnt[cur[buc[ctp].begin()->second]]--;
                cur[buc[ctp].begin()->second] -= buc[ctp].begin()->first - prv;
                cnt[cur[buc[ctp].begin()->second]]++;
                prv = buc[ctp].begin()->first;
                buc[ctp].erase(buc[ctp].begin());
            }
            if (buc[ctp].size())
            {
                cnt[cur[buc[ctp].begin()->second]]--;
                cur[buc[ctp].begin()->second] -= dep[x] - prv;
                cnt[cur[buc[ctp].begin()->second]]++;
            }
            buc[ctp].emplace(dep[x], y);
            x = f[tp[x]];
        }
        // cerr << cnt[0] << '\n';
        cout << cnt[z] << '\n';
        // for (int j = 0; j <= c; j++)
        //  cout << cur[j] << " \n"[j == c];
    }
}
int main()
{
#ifdef Redshift_Debug
    auto st = chrono::high_resolution_clock::now();
#endif
    run();
#ifdef Redshift_Debug
    auto ed = chrono::high_resolution_clock::now();
    fprintf(stderr, "%.9lf\n", (ed - st).count() / 1e9);
#endif
}