HDU 5957 Query on a graph

2016ACM/ICPC亚洲区沈阳站

题意

• \(N(N \le 10^5)\)个点，\(N\)条边的连通图。
• 有\(M \le 10^5\)操作：

1. \(MODIFY\ u\ k\ d，k \le 2\)：距离点\(u\)不超过\(k\)的点的权值都加上\(d\)。
2. \(QUERY\ u\ k\)：询问距离\(d\)不超过\(k\)的点权和。

思路

• 图的形状时一个环和若干树枝构成。
• 考虑\(k=1\)时，分两种情况讨论：

1. \(u\)在环上，则需要累加环上相邻两点权值，以及树枝上深度为1的所有点的权值，并且这些点的bfs序是连续的，那么显然可以用线段树维护权值和。
2. \(u\)不在环上时，累加父亲节点的权值以及树枝深度为1的点权。

• 记\(Q1(u)\)表示距离\(u\)不超过1的权值和。
• 当\(k=2\)时，树枝上距离为2的点的bfs序也是连续的，所以同样用线段树维护，若\(u\)不在环上，累加上\(Q1(f_u)-w_u\)即可；若\(u\)在环上，求出\(Q1(v_1)+Q1(v_2)-2w_u\)，\(v_1、v_2\)表示换上与\(u\)相邻的点，显然\(u\)被重复计数两次。
• 当环的长度分别为3、4时，\(Q1(v_1)、Q2(v_2)\)存在交集，需要扣除重复计数的值。

#include
    
     using namespace std;typedef long long ll;typedef unsigned long long ul;#define sz(x) ((int)(x).size())#define rep(i,l,r) for(int i=(l),I=(r);i
     
      > 1;        sum[ls] += add[t] * (m - l + 1), add[ls] += add[t];        sum[rs] += add[t] * (r - m), add[rs] += add[t];        add[t] = 0;    }}void build(int t, int l, int r) {    sum[t] = add[t] = 0;    if (l < r) {        int m = (l + r) >> 1;        build(ls, l, m), build(rs, m + 1, r);    }}inline void upd(int t, int l, int r, int L, int R, ll v) {    if (R < l || r < L || L > R)        return ;    if (L <= l && r <= R) {        sum[t] += (r - l + 1) * v, add[t] += v;        return ;    }    down(t, l, r);    int m = (l + r) >> 1;    upd(ls, l, m, L, R, v), upd(rs, m + 1, r, L, R, v);    up(t);}inline ll qry(int t, int l, int r, int L, int R) {    if (R < l || r < L || L > R)        return 0;    if (L <= l && r <= R)        return sum[t];    down(t, l, r);    int m = (l + r) >> 1;    ll ret = qry(ls, l, m, L, R) + qry(rs, m + 1, r, L, R);    up(t);    return ret;}int n, q, tot, f[N], pos[N], deg[N], L[N][3], R[N][3];vector
      
        cir, e[N];void bfs() {    queue
       
         que;    rep(i, 1, n + 1)        if (deg[i] == 1)            que.push(i);    while (!que.empty()) {        int u = que.front();        que.pop();        rep(i, 0, sz(e[u])) {            int v = e[u][i];            --deg[v];            if (deg[v] == 1)                que.push(v);        }    }    rep(i, 1, n + 1)        deg[i] = (deg[i] == 2);    cir.clear();    rep(i, 1, n + 1)        if (deg[i]) {            int u = i;            do {                rep(j, 0, sz(e[u])) {                    int v = e[u][j];                    if (deg[v] && (cir.empty() || v != cir.back())) {                        pos[u] = sz(cir);                        cir.push_back(u);                        u = v;                        break;                    }                }            } while (u != i);            break;        }}int que[N];void BFS(int s) {    int h = 0, t = 0;    que[t++] = s, f[s] = -1;    while (h < t) {        int u = que[h++];        L[u][0] = R[u][0] = ++tot;        L[u][1] = L[u][2] = n + 1, R[u][1] = R[u][2] = 0;        rep(i, 0, sz(e[u])) {            int v = e[u][i];            if (v == f[u] || deg[v])                continue;            f[v] = u, que[t++] = v;        }    }    for (int i = t - 1; i > 0; --i) {        int v = que[i];        int u = f[v];        L[u][1] = min(L[u][1], L[v][0]), R[u][1] = max(R[u][1], R[v][0]);        u = f[u];        if (u == -1)            continue;        L[u][2] = min(L[u][2], L[v][0]), R[u][2] = max(R[u][2], R[v][0]);    }    //    printf("u = %d, ", u);    //    rep(i, 0, 3) printf("(%d, %d) ", L[u][i], R[u][i]);puts("");}char op[20];inline ll Q0(int u) {    return qry(1, 0, tot, L[u][0], R[u][0]);}inline ll Q1(int u) {    ll ans = Q0(u) + qry(1, 0, tot, L[u][1], R[u][1]);    if (deg[u]) {        ans += Q0(cir[(pos[u] + 1) % sz(cir)]);        ans += Q0(cir[(pos[u] - 1 + sz(cir)) % sz(cir)]);    } else {        ans += Q0(f[u]);    }    return ans;}inline void A0(int u, ll v) {    upd(1, 0, tot, L[u][0], R[u][0], v);}inline void A1(int u, ll v) {    A0(u, v), upd(1, 0, tot, L[u][1], R[u][1], v);    if (deg[u]) {        A0(cir[(pos[u] + 1) % sz(cir)], v);        A0(cir[(pos[u] - 1 + sz(cir)) % sz(cir)], v);    } else {        A0(f[u], v);    }}int main() {    int T;    scanf("%d", &T);    rep(cas, 0, T) {        scanf("%d", &n);        rep(i, 1, n + 1)            deg[i] = 0, e[i].clear();        rep(i, 0, n) {            int u, v;            scanf("%d%d", &u, &v);            ++deg[u], ++deg[v];            e[u].push_back(v), e[v].push_back(u);        }        bfs();        tot = 0;        rep(i, 1, n + 1)             if (deg[i])                BFS(i);        build(1, 0, tot);        scanf("%d", &q);        rep(_q, 0, q) {            scanf(" %s", op);            if (op[0] == 'M') {                int u, k, d;                scanf("%d%d%d", &u, &k, &d);                if (k == 0) {                    A0(u, d);                } else if (k == 1) {                    A1(u, d);                } else if (k == 2) {                    A0(u, d), upd(1, 0, tot, L[u][1], R[u][1], d), upd(1, 0, tot, L[u][2], R[u][2], d);                    if (deg[u]) {                        int v1 = cir[(pos[u] + 1) % sz(cir)];                        int v2 = cir[(pos[u] - 1 + sz(cir)) % sz(cir)];                        A1(v1, d), A1(v2, d), A0(u, -2 * d);                        if (sz(cir) == 3) {                            A0(v1, -d), A0(v2, -d);                        } else if (sz(cir) == 4) {                            A0(cir[(pos[u] + 2) % sz(cir)], -d);                        }                    } else {                        A1(f[u], d), A0(u, -d);                    }                }            } else {                int u, k;                scanf("%d%d", &u, &k);                ll ans = 0;                if (k == 0) {                    ans = Q0(u);                } else if (k == 1) {                    ans = Q1(u);                } else if(k == 2) {                    ans = Q0(u) + qry(1, 0, tot, L[u][1], R[u][1]) + qry(1, 0, tot, L[u][2], R[u][2]);                    if (deg[u]) {                        int v1 = cir[(pos[u] + 1) % sz(cir)];                        int v2 = cir[(pos[u] - 1 + sz(cir)) % sz(cir)];                        ans += Q1(v1) + Q1(v2) - 2ll * Q0(u);                        if (sz(cir) == 3) {                            ans -= Q0(v1) + Q0(v2);                        } else if (sz(cir) == 4) {                            ans -= Q0(cir[(pos[u] + 2) % sz(cir)]);                        }                    } else {                        ans += Q1(f[u]) - Q0(u);                    }                }                printf("%lld\n", ans);            }        }    }    return 0;}