【2020年牛客暑假第七场】C题 A National Pandemic

传送门：https://ac.nowcoder.com/acm/contest/5672/C

题意

给一棵树，每个节点的初始权值为0，有以下三种操作：

• $1\; x\; w$，将所以点的权值都加上w-dis(x,y)，dis为x到y的最短路径的边数
• $2\; x$，将x点与0取较小值min(x, 0)。
• $3\; x$，查询x点的权值。

思路

第一个操作中，不难想到与LCA的联系，即：

$=w-dis(1,x)-dis(1,y)+dis(1, lca(x, y))$ $=w-dep[x]-dep[y]+dis[lca(x,y)]$

这里的dep[1]是从0开始算的，不是dep[1] =1;

每次操作1的时候，都会对每个点增加w-dep[x]和减去每个点的dep[y] 所以用一个全局变量Sum维护w-dep[x]，用num维护的操作一的次数即可。

那么怎么维护dis[lca(x,y)]呢？先来看看这个图：

所以我们不用每次求两个点的LCA，那样做复杂度爆炸!

我们只需要将根节点1到节点x之间的简单路径每次增加2即可。

因为对于其他点，当我们查询dis(1,y)时，只增加经过lca到节点1之间的权值，而y到lca之间的权值没有增加，我们也不想要增加，这样就得到我们想要的效果。

对于维护树上路径的权值，我们可以先轻重链剖分，再用线段树维护即可。

==注意：我们用线段树维护的是树上路径的点权值，而不是边权值，dis是边数，又n个点有n-1条边，也就是每次进行操作一的时候重复加上1个2了，所以我们减去num*2。==

对于操作2，只有x的权值>0时，才会与0进行比较。

可以先求出x点的权值，如果大于0，开一个del数组维护一下 即$del[x] += (f > 0 ?: f:0)$

这样做之后，每次求权值的时候都减去del[x]就行了。

最后注意一下初始化就ac了。

Code（336MS）

##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

// const ll mod = 998244353;
// const ll mod = 1e9 + 7;
// const double eps = 1e-6;
// const double PI = acos(-1);
// const double R = 0.57721566490153286060651209;

const int N = 1e5 + 10;

/*-----------------建边-----------------*/

struct Edge {
    int v, next;
}e[N << 1];
int head[N], cnt;

inline void add(int u, int v) {
    e[++cnt].v = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}

/*----------------轻重链剖分----------------*/

int siz[N], fa[N], dep[N], son[N];

void dfs1(int u, int par) {
    dep[u] = dep[fa[u] = par] + (siz[u] = 1);
    for(int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == par) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if(!son[u]  siz[v] > siz[son[u]])
            son[u] = v;
    }
}

int top[N], nodeof[N], dfn[N], tim;

void dfs2(int u, int topf) {
    nodeof[dfn[u] = ++tim] = u;
    top[u] = topf;
    if(!son[u]) return ;
    dfs2(son[u], topf);
    for(int i = head[u];i ; i = e[i].next) {
        int v = e[i].v;
        if(v == son[u]  v == fa[u]) continue;
        dfs2(v, v);
    }
}

##define lc u << 1
##define rc u << 1  1
##define mid (t[u].l + t[u].r) / 2

/*-----------线段树------------------*/

struct Node {
    int l, r;
    ll sum, tag;
}t[N << 2];

void push_up(int u) {
    t[u].sum = t[lc].sum + t[rc].sum;
}

void push_down(int u) {
    if(!t[u].tag) return ;
    t[lc].sum += t[u].tag * (t[lc].r - t[lc].l + 1);
    t[rc].sum += t[u].tag * (t[rc].r - t[rc].l + 1);
    t[lc].tag += t[u].tag;
    t[rc].tag += t[u].tag;
    t[u].tag = 0;
}

void build(int u, int l, int r) {
    t[u].l = l; t[u].r = r; t[u].tag = t[u].sum = 0;
    if(l == r) {
        return ;
    }
    int m = (l + r) >> 1;
    build(lc, l, m);
    build(rc, m + 1, r);
}

void modify(int u, int ql, int qr, ll v) {
    if(ql <= t[u].l && t[u].r <= qr) {
        t[u].sum += (t[u].r - t[u].l + 1) * v;
        t[u].tag += v;
        return ;
    }
    push_down(u);
    if(ql <= mid) modify(lc, ql, qr, v);
    if(qr > mid)  modify(rc, ql, qr, v);
    push_up(u);
}

ll query(int u, int ql, int qr) {
    if(ql <= t[u].l && t[u].r <= qr) {
        return t[u].sum;
    }
    push_down(u);
    ll ans = 0;
    if(ql <= mid) ans += query(lc, ql, qr);
    if(qr > mid)  ans += query(rc, ql, qr);
    return ans;
}

void modify_chain(int x, int y, int val) {
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        modify(1, dfn[top[x]], dfn[x], val);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    modify(1, dfn[x], dfn[y], val);
}

ll query_chain(int x, int y) {
    ll ans = 0;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        ans += query(1, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    ans += query(1, dfn[x], dfn[y]);
    return ans;
}

ll Sum, num;
ll del[N];

void init() {
    cnt = tim = Sum = num = 0;
    mem(dfn, 0);
    mem(siz, 0);
    mem(e, 0);
    mem(son, 0);
    mem(del, 0);
    mem(dep, -1);
    mem(head, 0);
}

void solve() {
    int _; cin >> _;
    while(_--) {
        init();
        int n, m;
        cin >> n >> m;
        for(int i = 1;i <= n - 1; i++) {
            int u, v;
            cin >> u >> v;
            add(u, v);
            add(v, u);
        }
        dfs1(1, 0);
        dfs2(1, 1);
        build(1, 1, n);
        // w - dep[x] - dep[y] + 2 * dep[lca(x, y)]
        while(m--) {
            int opt; cin >> opt;
            if(opt == 1) {
                int x, val; cin >> x >> val;
                Sum += val - dep[x];
                num++;
                modify_chain(1, x, 2);
            }
            else if(opt == 2) {
                int x; cin >> x;
                ll f = Sum - num * dep[x] + query_chain(1, x) - del[x] - 2 * num;
                if(f > 0) del[x] += f;
            }
            else if(opt == 3) {
                int x; cin >> x;
                cout << Sum - num * dep[x] + query_chain(1, x) - del[x] - 2 * num << endl;
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    signed test_index_for_debug = 1;
    char acm_local_for_debug = 0;
    do {
        if (acm_local_for_debug == '$') exit(0);
        if (test_index_for_debug > 20)
            throw runtime_error("Check the stdin!!!");
        auto start_clock_for_debug = clock();
        solve();
        auto end_clock_for_debug = clock();
        cout << "Test " << test_index_for_debug << " successful" << endl;
        cerr << "Test " << test_index_for_debug++ << " Run Time: "
             << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
        cout << "--------------------------------------------------" << endl;
    } while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
##else
    solve();
##endif
    return 0;
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/12/10/2020-nowcoder-shujia7-c/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！