2019ICPC上海网络赛A 边分治+线段树

女爷i 2023-06-04 11:52 21阅读 0赞

题目：

给定一棵树， 带边权。

现在有2种操作：

1.修改第i条边的权值。

2.询问u到其他一个任意点的最大距离是多少。

解法：边分治+线段树

首先我们将所有的点修改和边修改都存在对应的边里面。

然后接下来就是边分治的过程。

对于边分治的一层来说，以这条边为界分割出来。

设这条边为 x, y, w

我们把这层图上所有的边修改， 点询问都拿出来， 按照修改时间排序一下。

在切掉这条边的基础上。

然后以x为根， dfn建立一棵线段树， 记下边修改是修改在那个子树上的。

然后以y为根， dfn建立一棵线段树， 记下边修改是修改在那个子树上的。

然后对于一个修改操作来说， 就是相当于修改这颗子树的所有点的权值。

对于一个询问操作来说， 就是询问这个点到这边根的距离 + 中间这条边 + 另一边的最大值。

注意的是， 记得维护中间这条边的修改。

为了排除虚点的影响， 我就把虚点的权值设为-inf了，但是感jio是可以不用这样搞的。

总复杂度分析：

每个点只会出现在log个子图内， 每个修改和询问也最多是出现在这log个子图内。

每幅图sort + 线段树操作1次。

所以是 n \* log + q \* log \* log。

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
    #define LL long long
    #define ULL unsigned LL
    #define fi first
    #define se second
    #define pb push_back
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lch(x) tr[x].son[0]
    #define rch(x) tr[x].son[1]
    #define max3(a,b,c) max(a,max(b,c))
    #define min3(a,b,c) min(a,min(b,c))
    typedef pair<int,int> pll;
    const int inf = 0x3f3f3f3f;
    const LL INF = 0x3f3f3f3f3f3f3f3f;
    const LL mod =  (int)1e9+7;
    const int N = 2e5 + 100;
    struct Node{
        int head[N], to[N<<1], nt[N<<1], ct[N<<1], id[N<<1];
        int tot;
        void init(){
            memset(head, -1, sizeof(head));
            tot = 0;
        }
        void add(int u, int v, int cost, int fid){
            ct[tot] = cost;
            to[tot] = v;
            nt[tot] = head[u];
            id[tot] = fid;
            head[u] = tot++;
        }
    }e[2];
    int n, maxn, m, white[N], cut[N<<1];
    void rebuild(int o, int u){
        int ff = 0;
        for(int i = e[0].head[u]; ~i; i = e[0].nt[i]){
            int v = e[0].to[i];
            if(o == v) continue;
            if(!ff){
                e[1].add(u, v, e[0].ct[i], e[0].id[i]);
                e[1].add(v, u, e[0].ct[i], e[0].id[i]);
                ff = u;
            }
            else {
                ++n;
                e[1].add(ff, n, 0, 0); e[1].add(n, ff, 0, 0);
                e[1].add(n, v, e[0].ct[i], e[0].id[i]); e[1].add(v, n, e[0].ct[i], e[0].id[i]);
                ff = n;
            }
            rebuild(u, v);
        }
    }
    
    int sz[N], minval, id;
    void get_edge(int o, int u, int num){
        sz[u] = 1;
        for(int i = e[1].head[u]; ~i; i = e[1].nt[i]){
            int v = e[1].to[i];
            if(v == o || cut[i>>1]) continue;
            get_edge(u, v, num);
            sz[u] += sz[v];
            int tmp = max(sz[v], num - sz[v]);
            if(tmp < minval){
                minval = tmp;
                id = i;
            }
        }
    }
    int k = 0, op;
    int qtot = 0;
    pll P[N<<2];
    int L[N];
    vector<pll> edge[N];
    vector<pll> Que[N];
    LL ans[N];
    int col[N];
    int ecol[N];
    struct GG{
        LL a[N];
        LL seg[N<<2], lazy[N<<2];
        int point[N];
        int edis[N];
        int tot = 0;
        int dfn[N], out[N], fdfn[N];
        void dfs(int o, int u, LL dis){
            sz[u] = 1;
            dfn[u] = ++tot;
            fdfn[tot] = u;
            col[u] = op;
            if(u > maxn)
                a[tot] = -INF;
            else
                a[tot] = dis;
            for(pll & t : Que[u])
                P[++qtot] = t;
            for(int i = e[1].head[u]; ~i; i = e[1].nt[i]){
                int v = e[1].to[i];
                if(v == o || cut[i>>1]) continue;
                ecol[e[1].id[i]] = op;
                point[e[1].id[i]] = v;
                edis[e[1].id[i]] = e[1].ct[i];
                for(pll & t : edge[e[1].id[i]]){
                    P[++qtot] = t;
                }
                dfs(u, v, dis + e[1].ct[i]);
                sz[u] += sz[v];
            }
            out[u] = tot;
    
        }
        void Build(int l, int r, int rt){
            lazy[rt] = 0;
            if(l == r){
                seg[rt] = a[l];
                return ;
            }
            int m = l+r >> 1;
            Build(lson); Build(rson);
            seg[rt] = max(seg[rt<<1], seg[rt<<1|1]);
        }
        void Tree_Build(){
            Build(1, tot, 1);
        }
        void PushDown(int rt){
            if(lazy[rt]){
                lazy[rt<<1] += lazy[rt];
                lazy[rt<<1|1] += lazy[rt];
                seg[rt<<1] += lazy[rt];
                seg[rt<<1|1] += lazy[rt];
                lazy[rt] = 0;
            }
        }
        void Update(int L, int R, int C, int l, int r, int rt){
            if(L <= l && r <= R){
                seg[rt] += C;
                lazy[rt] += C;
                return ;
            }
            int m = l+r >> 1;
            PushDown(rt);
            if(L <= m) Update(L, R, C, lson);
            if(m <  R) Update(L, R, C, rson);
            seg[rt] = max(seg[rt<<1], seg[rt<<1|1]);
        }
        void Tree_Update(int id, int ct){
            int u = point[id];
            Update(dfn[u], out[u], ct-edis[id], 1, tot, 1);
            edis[id] = ct;
        }
        LL Query(int L, int l, int r, int rt){
            if(l == r) return seg[rt];
            PushDown(rt);
            int m = l+r >> 1;
            if(L <= m) return Query(L, lson);
            return Query(L, rson);
        }
        LL Tree_Query(int x){
            return Query(dfn[x], 1, tot, 1);
        }
        void init(){
            tot = 0;
        }
    }Seg[2];
    void solve(int u, int num){
    //    cout << u << " " << num << endl;
        if(num <= 1) return ;
        minval = inf;
        get_edge(0, u, num);
        int nid = id;
        cut[nid>>1] = 1;
        qtot = 0;
        op = 0;
        Seg[0].init();
        Seg[0].dfs(0, e[1].to[nid], 0);
        Seg[0].Tree_Build();
        op = 1;
        Seg[1].init();
        Seg[1].dfs(0, e[1].to[nid ^ 1], 0);
        Seg[1].Tree_Build();
        int gid = e[1].id[nid];
        for(pll & t : edge[gid])
            P[++qtot] = t;
        sort(P+1, P+1+qtot);
        for(int i = 1; i <= qtot; ++i){
            if(P[i].se < 0){
                int u = -P[i].se;
                if(u == gid)
                    e[1].ct[nid] = L[P[i].fi];
                else
                    Seg[ecol[u]].Tree_Update(u, L[P[i].fi]);
            }
            else {
                int u = P[i].se;
                int id = col[u];
                ans[P[i].fi] = max(ans[P[i].fi], Seg[id].Tree_Query(u) + Seg[id^1].seg[1] + e[1].ct[nid]);
            }
        }
        solve(e[1].to[nid], sz[e[1].to[nid]]);
        solve(e[1].to[nid^1], sz[e[1].to[nid^1]]);
    }
    int main(){
        e[0].init(), e[1].init();
        scanf("%d", &n);
        maxn = n;
        for(int i = 1, u, v, w; i < n; ++i){
            scanf("%d%d%d", &u, &v, &w);
            e[0].add(u, v, w, i);
            e[0].add(v, u, w, i);
        }
        int q, u;
        char s[4];
        scanf("%d", &q);
        for(int i = 1; i <= q; ++i){
            ans[i] = -1;
            scanf("%s", s);
            if(s[0] == 'Q'){
                scanf("%d", &u);
                Que[u].pb(pll(i, u));
            }
            else {
                scanf("%d%d", &u, &L[i]);
                edge[u].pb(pll(i, -u));
            }
        }
        rebuild(0, 1);
    //    cout << n << endl;
        solve(1, n);
        for(int i = 1; i <= q; ++i){
            if(~ans[i])
                printf("%lld\n", ans[i]);
        }
        return 0;
    }
    /*
    2
    1 2 1
    3
    Q 1
    Q 1
    C 1 6
    */

转载于:https://www.cnblogs.com/MingSD/p/11527004.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/c5b1a5da6afd4fa087b59274040d7402.png