The Preliminary Contest for ICPC Asia Shanghai 2019 A. Lightning Routing I

Description:

The Lightning Network is a "Layer 2" payment protocol that operates on top of a blockchain-based cryptocurrency (like Bitcoin). It enables fast transactions between participating nodes and has been touted as a solution to the Bitcoin scalability problem. It features a peer-to-peer system for making micropayments of cryptocurrency through a network of bidirectional payment channels without delegating custody of funds.

In this problem, we'll regard the Lightning Network as a tree. And due to the network environment, the cost of these payment channels are changeable. That says, you are given a weighted undirected tree on $n$ vertices and $q$ queries. Each changes the weight of one edge or query the furthest distance of one vertex to another vertex. The distance between two vertices is the sum of the weights on the unique simple path that connects them.

Input:

The first line contains an integer $n$ $(1 \le n \le 10^5)$ --- the number of vertices in the tree.

Following $n-1$ lines will contain the initial structure of the tree. The $i$-th of these lines contains three space-separated integers $x_i, y_i, w_i$ $(1\leq x_i, y_i \leq n, 0\leq w_i \leq 10^9)$ meaning that initially, there is an edge between vertices $x_i$ and $y_i$ with weight $w_i$ . It is guaranteed that these $n-1$ lines describe a tree.

The next line contains an integer $q$ $(1 \le q \le 10^5)$ --- the number of qeries.Finally, $q$ lines describing queries follow. The $i$-th of these lines contains either 'Q $v_i$' or 'C $e_i$ $w_i$'.

  • C $e_i$ $w_i$ $(1 \leq e_i \leq n-1, 0\leq w_i \leq 10^9)$ , changes the weight of the $e_i$-th edge to $w_i$ , or
  • Q $v_i$ $(1 \leq v_i \leq n)$ , query the furthest distance of the vertex $v_i$ to another vertex.

Output:

Output the query for each query.

Sample Input:

5
1 2 1
1 3 1
2 4 1
2 5 1
3
Q 1
C 1 2
Q 2

Sample Output:

2
3

题目链接

对一棵 $n$ 个节点的树支持修改和查询两种操作,修改任一边权、查询距某点的最大边权和

这道题目的数据应该不是很强(树高不足),我的做法并不是正解

首先求出树的dfs序,并用线段树维护 $n$ 个节点到指定根节点( $1$ )节点的距离

对每次修改操作修改其边上深度较大点子树所有节点到指定根节点( $1$ )节点的距离

处理询问的话就按照深度降序不断枚举询问点的 $LCA$ ,在dfs序相应区间内利用公式 $dis(u,v)=dis(u,root)+dis(v,root)-2 \times dis(LCA(u,v),root)$ 计算维护最远距离

AC代码:

#include <bits/stdc++.h>
const int maxn = 1e5 + 5;
const long long inf = 1e18 + 5;
int n, m;
struct SaveEdge { int u, v, c; };
SaveEdge edge[maxn];
struct Edge { int v, c; };
std::vector<Edge> g[maxn];
int dfs_clock, fa[maxn], in[maxn], out[maxn], ele[maxn], dep[maxn];
long long dis[maxn];
void DfsSeq(int u, int p, int d_p, long long d_s) {
    fa[u] = p; dis[u] = d_s; dep[u] = d_p;
    in[u] = ++dfs_clock; ele[dfs_clock] = u;
    for (auto &e : g[u]) {
        int v = e.v, c = e.c;
        if (v == p) continue;
        DfsSeq(v, u, d_p + 1, d_s + c);
    }
    out[u] = dfs_clock;
}
long long tree[maxn * 4], lazy[maxn * 4];
void Pull(int o) {
    tree[o] = std::max(tree[o * 2], tree[o * 2 + 1]);
}
void Push(int o) {
    if (lazy[o] != 0) {
        tree[o * 2] += lazy[o];
        tree[o * 2 + 1] += lazy[o];
        lazy[o * 2] += lazy[o];
        lazy[o * 2 + 1] += lazy[o];
        lazy[o] = 0;
    }
}
void Build(int o, int l, int r) {
    tree[o] = lazy[o] = 0;
    if (l == r) {
        tree[o] = dis[ele[l]];
        return;
    }
    int mid = (l + r) / 2;
    Build(o * 2, l, mid);
    Build(o * 2 + 1, mid + 1, r);
    Pull(o);
}
void Modify(int o, int l, int r, int ll, int rr, int v) {
    if (ll <= l && rr >= r) {
        tree[o] += v;
        lazy[o] += v;
        return;
    }
    Push(o);
    int mid = (l + r) / 2;
    if (ll <= mid) Modify(o * 2, l, mid, ll, rr, v);
    if (rr > mid) Modify(o * 2 + 1, mid + 1, r, ll, rr, v);
    Pull(o);
}
void Modify(int ll, int rr, int v) {
    Modify(1, 1, n, ll, rr, v);
}
long long Query(int o, int l, int r, int ll, int rr) {
    if (ll <= l && rr >= r) return tree[o];
    Push(o);
    int mid = (l + r) / 2;
    long long ret = -inf;
    if (ll <= mid) ret = std::max(ret, Query(o * 2, l, mid, ll, rr));
    if (rr > mid) ret = std::max(ret, Query(o * 2 + 1, mid + 1, r, ll, rr));
    return ret;
}
long long Query(int ll, int rr) {
    if (rr < ll) return 0;
    return Query(1, 1, n, ll, rr);
}
int main() {
    scanf("%d", &n);
    for (int i = 1, u, v, c; i < n; ++i) {
        scanf("%d%d%d", &u, &v, &c);
        g[u].push_back((Edge){v, c});
        g[v].push_back((Edge){u, c});
        edge[i] = (SaveEdge){u, v, c};
    }
    DfsSeq(1, 0, 1, 0);
    Build(1, 1, n);
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i) {
        char op[2];
        scanf("%s", op);
        if (op[0] == 'C') {
            int e, c;
            scanf("%d%d", &e, &c);
            int u = edge[e].u, v = edge[e].v, lastc = edge[e].c;
            if (dep[u] > dep[v]) std::swap(u, v);
            Modify(in[v], out[v], c - lastc);
            edge[e].c = c;
        }
        else if (op[0] == 'Q') {
            int u;
            scanf("%d", &u);
            long long ori = Query(in[u], in[u]);
            long long ans = Query(in[u], out[u]) - ori;
            int _fa = fa[u], _son = u;
            while (_fa != 0) {
                long long pre = Query(in[_fa], in[_fa]), tmp = std::max(Query(in[_fa], in[_son] - 1), Query(out[_son] + 1, out[_fa]));
                ans = std::max(ans, ori + tmp - 2ll * pre);
                _son = _fa; _fa = fa[_son];
            }
            printf("%lld\n", ans);
        }
    }
    return 0;
}
Last modification:September 18th, 2019 at 01:23 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment