Chlience

【题解】LOJ 2049 「HNOI2016」网络
Problem给定一棵无根树,两个节点之间可能出现一个链接,当然也有可能消失,每个链接有一个重要度,现在每个时刻可...
扫描右侧二维码阅读全文
09
2019/02

【题解】LOJ 2049 「HNOI2016」网络

Problem

给定一棵无根树,两个节点之间可能出现一个链接,当然也有可能消失,每个链接有一个重要度,现在每个时刻可能有三种操作

  1. 某两个服务器之间出现一个链接
  2. 某个链接断开
  3. 某个服务器故障

问故障时没有被影响的最大重要度链接是多少

Thought

这个题比较 naive

每次加入一个链接相当于在整棵树除了两个节点间的路径全部加上一个贡献
然后维护这两个节点的路径,自然的想到树链剖分

最后在线段树上套一个堆(带删除
每次查询当前节点堆中最大值即可

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
struct edge {
    int t, n;
} e[N << 1];
struct LIAN {
    int l, r;
} lian[N];
struct Q {
    int l, r;
    int val;
} q[N << 1];
struct tree {
    priority_queue<int> q1, q2;
    void ins(int a) { q1.push(a); }
    void del(int a) { q2.push(a); }
    int get() {
        while (!q2.empty() && (q1.top() == q2.top())) {
            q1.pop();
            q2.pop();
        }
        if (!q1.empty())
            return q1.top();
        else
            return -1;
    }
} t[N << 2];
int head[N], tot;
int top[N], id[N], fa[N], son[N], siz[N], dep[N], cnt;
int n, m, cpt;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
bool cmp(LIAN a, LIAN b) { return a.l < b.l; }
void addedge(int u, int v) {
    e[++ tot] = {v, head[u]};
    head[u] = tot;
}
void dfs1(int x, int f) {
    fa[x] = f;
    dep[x] = dep[fa[x]] + 1;
    siz[x] = 1;
    int maxson = -1;
    for (int i = head[x]; i; i = e[i].n) {
        if (e[i].t == fa[x])
            continue;
        dfs1(e[i].t, x);
        siz[x] += siz[e[i].t];
        if (siz[e[i].t] > maxson) {
            son[x] = e[i].t;
            maxson = siz[e[i].t];
        }
    }
}
void dfs2(int x, int tophead) {
    id[x] = ++cnt;
    top[x] = tophead;
    if (!son[x])
        return;
    dfs2(son[x], tophead);
    for (int i = head[x]; i; i = e[i].n) {
        if (e[i].t == fa[x] || e[i].t == son[x])
            continue;
        dfs2(e[i].t, e[i].t);
    }
}
void update(int x, int l, int r, int L, int R, int val) {
    if (L <= l && r <= R) {
        if (cpt == 0)
            t[x].ins(val);
        else
            t[x].del(val);
        return;
    }
    int mid = (l + r) >> 1;
    if (L <= mid)
        update(x << 1, l, mid, L, R, val);
    if (R > mid)
        update((x << 1) + 1, mid + 1, r, L, R, val);
}
void ins(int x, int y, int val) {
    int total = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        lian[++total] = (LIAN){ id[top[x]], id[x] };
        x = fa[top[x]];
    }
    if (dep[x] > dep[y])
        swap(x, y);
    lian[++total] = (LIAN){ id[x], id[y] };
    sort(lian + 1, lian + total + 1, cmp);
    int last = 0;
    for (int i = 1; i <= total; i++) {
        if (last + 1 <= lian[i].l - 1)
            update(1, 1, n, last + 1, lian[i].l - 1, val);
        last = lian[i].r;
    }
    if (last + 1 <= n)
        update(1, 1, n, last + 1, n, val);
}
void query(int x, int l, int r, int P, int &ans) {
    ans = max(ans, t[x].get());
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (P <= mid)
        query(x << 1, l, mid, P, ans);
    else
        query((x << 1) + 1, mid + 1, r, P, ans);
}
int main() {
    n = read(); m = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        addedge(u, v);
        addedge(v, u);
    }
    int rt = rand() % n + 1;
    dfs1(rt, 0);
    dfs2(rt, rt);
    for (int i = 1; i <= m; i++) {
        cpt = read();
        if (cpt == 0) {
            q[i].l = read();
            q[i].r = read();
            q[i].val = read();
            ins(q[i].l, q[i].r, q[i].val);
        } else if (cpt == 1) {
            int x = read();
            ins(q[x].l, q[x].r, q[x].val);
        } else {
            int x = read(), ans = - 1;
            query(1, 1, n, id[x], ans);
            printf("%d\n", ans);
        }
    }
    return 0;
}
Last modification:February 9th, 2019 at 09:42 am

Leave a Comment