SP2666Solution

SrsgPrince_ · 2023-05-28 09:58:35 · 题解

QTREE4 - Query on a tree IV Solution

题面传送门：QTREE4 - Query on a tree IV。

推荐在 博客 中查看。

题目分析 Hint

题目中让我们进行两个操作：

1. C a 将点 a 的颜色反转。（黑变白，白变黑）

2. A 询问 dist(a,b) 的最大值。a,b 点都必须为白色（a 与 b 可以相同），显然如果树上仍存在白点，查询得到的值一定是个非负数。特别地，如果 A 操作时树上没有白点，输出 They have disappeared.。

第一个操作是修改颜色，第二个操作是维护边权。考虑用树链剖分做。

思路 Solution

先对原树进行树链剖分，并且对重链建树。建树的方法很简单，先令 dep_u 为 点 u 到根节点的距离，dist(u, v) 为点 u 到点 v 的距离，mx1_u 为点 u 向下第一步不走重边能走到的最远的白点的距离，mx2_u 为点 u 向下第一步不走重边能走到的次远的白点的距离。我们用堆来维护 mx1_u，求出 u 的轻儿子在重链线段树的 lmax 就可以了。\operatorname{pushUp()} 需要维护三个值 lmax，rmax 和 mx，分别是 lmax = \max{(lson_{lmax}, rson_{lmax} + dep_{rnk_{mid+1}} - dep_{rnk_{l}})} rmax = \max{(rson_{rmax}, lson_{rmax} + dep_{rnk_{r}} - dep_{rnk_{mid}})} mx = \max{(\max(lson_{mx}, rson_{mx}), lson_{rmax} + rson_{lmax} + dep_{rnk_{mid + 1}} - dep_{rnk_{mid}})}

也就是如下代码。

inline void pushUp(int p, int lft, int rgt) {
    int ls = tr[p].lson, rs = tr[p].rson, mid = (lft + rgt) >> 1;
    tr[p].lmax = max(tr[ls].lmax, tr[rs].lmax + dep[rnk[mid + 1]] - dep[rnk[lft]]);
    tr[p].rmax = max(tr[rs].rmax, tr[ls].rmax + dep[rnk[rgt]] - dep[rnk[mid]]);
    tr[p].mx = max(max(tr[ls].mx, tr[rs].mx), tr[ls].rmax + tr[rs].lmax + dep[rnk[mid + 1]] - dep[rnk[mid]]);
}

接下来是修改点的颜色。修改一个点的颜色，要先修改当前点所在的重链线段树上进行修改。我们还是用一个堆来进行维护，可以 O(1) 查询，线段树的复杂度 O(\log n)，堆的复杂度 O(\log n)。那么整体就是 O(q \log ^ 2 n)，其中 q 为询问次数。

这里给出代码。

struct Edge {
    int des, w;
};
vector<Edge> ed[maxn];
inline void dfs1(int x, int fth) {
    siz[x] = 1, son[x] = -1;
    for (auto y : ed[x]) {
        if (y.des == fth) continue;
        dep[y.des] = dep[x] + y.w, fa[y.des] = x, dfs1(y.des, x), siz[x] += siz[y.des];
        if (son[x] < 0 || siz[y.des] > siz[son[x]]) son[x] = y.des;
    }
}
inline void dfs2(int x, int tp) {
    top[x] = tp, dfn[x] = ++tme, rnk[tme] = x, len[tp]++;
    if (son[x] < 0) return;
    dfs2(son[x], tp);
    for (auto y : ed[x])
        if (y.des != son[x] && y.des != fa[x])
            dfs2(y.des, y.des);
}
struct Queue {
    priority_queue<int> q1, q2;
    inline void insert(int v) {if (v != -inf) q1.push(v);}
    inline void erase(int v) {if (v != -inf) q2.push(v);}
    inline int top() {
        while (1) {
            if (q1.empty()) return -inf;
            if (q2.empty() || q1.top() != q2.top()) return q1.top();
            q1.pop(), q2.pop();
        }
    }
}hp[maxn], res;
struct SegmentTree {
    int lson, rson, lmax, rmax, mx;
} tr[maxn << 2];
int tot, rt[maxn];
// 这里不在重复 pushUp
inline void buildTree(int &p, int lft, int rgt) {
    if (!p) p = ++tot;
    if (lft == rgt) {
        int x = rnk[lft];
        for (auto y : ed[x]) {
            if (y.des == fa[x] || y.des == son[x]) continue;
            hp[x].insert(tr[rt[y.des]].lmax + dep[y.des] - dep[x]);
        }
        int mx1 = hp[x].top(); hp[x].erase(mx1);
        int mx2 = hp[x].top(); hp[x].insert(mx1);
        tr[p].lmax = tr[p].rmax = max(0, mx1), tr[p].mx = max(0, max(mx1, mx1 + mx2));
        return;
    }
    int mid = (lft + rgt) >> 1;
    buildTree(tr[p].lson, lft, mid), buildTree(tr[p].rson, mid + 1, rgt);
    pushUp(p, lft, rgt);
}
inline void update(int p, int lft, int rgt, int id) {
    if (lft == rgt) {
        int x = rnk[lft];
        int mx1 = hp[x].top(); hp[x].erase(mx1);
        int mx2 = hp[x].top(); hp[x].insert(mx1);
        if (col[x]) tr[p].lmax = tr[p].rmax = mx1, tr[p].mx = mx1 + mx2;
        else tr[p].lmax = tr[p].rmax = max(0, mx1), tr[p].mx = max(0, max(mx1, mx1 + mx2));
        return;
    }
    int mid = (lft + rgt) >> 1;
    if (id <= mid) update(tr[p].lson, lft, mid, id);
    else update(tr[p].rson, mid + 1, rgt, id);
    pushUp(p, lft, rgt);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        ed[u].push_back({v, w});
        ed[v].push_back({u, w});
    }
    dfs1(1, 0);
    dfs2(1, 1);
    for (int i = n; i; --i) {
        int x = rnk[i];
        if (x != top[x]) continue;
        buildTree(rt[x], dfn[x], dfn[x] + len[x] - 1);
        res.insert(tr[rt[x]].mx);
    }
    int m;
    cin >> m;
    int cnt = n;
    while (m--) {
        char ch;
        cin >> ch;
        if (ch == 'A') {
            if (!cnt) cout << "They have disappeared.\n";
            else cout << res.top() << "\n";
            continue;
        }
        int x;
        cin >> x;
        col[x] ^= 1;
        if (!col[x]) cnt++; else cnt--;
        while (x) {
            int tp = top[x];
            res.erase(tr[rt[tp]].mx);
            if (fa[tp]) hp[fa[tp]].erase(tr[rt[tp]].lmax + dep[tp] - dep[fa[tp]]);
            update(rt[tp], dfn[tp], dfn[tp] + len[tp] - 1, dfn[x]);
            if (fa[tp]) hp[fa[tp]].insert(tr[rt[tp]].lmax + dep[tp] - dep[fa[tp]]);
            res.insert(tr[rt[tp]].mx);
            x = fa[tp];
        }
    }
    return 0;
}

也不知道为什么，我一开始 TLE 了两次，查过了所有的地方，都没问题，自造数据也没问题，最后不知道为什么改了输入输出，用了 cin/cout 然后就过了，快读快写反而没过，感觉是 putchar 在 SPOJ 里面寄了。