P3250 [hnoi2016] Network + [necpc2022] f.tree path tree section + segment tree maintenance heap

The ideas of the two questions are very similar , So focus on recording ideas and practices

P3250 [HNOI2016] The Internet

Topic analysis

Given a tree with $n$ Tree of nodes , Yes $m$ The following operations :

0 a b c It means that $(a,b)$ Add an importance of $c$ The edge of .

1 t Means delete the $t$ The edge added by this operation

2 x Representation node $x$ Something goes wrong . At this point, you need to answer , All without $x$ The greatest importance of the edges of the node .

First, weight the edge weight points , That is, problem serialization on the tree , Then use the segment tree to maintain the complement of the points to be checked . Because the segment tree node maintains the maximum value of the sequence , Therefore, open the node into a large root heap , Then each node records the maximum weight in the path that does not pass through the node , And deleted weights .

For each edge adding operation , Tree analysis LCA Find all the intervals occupied by the path , Then modify its complement . The complements can first sort the intervals obtained by tree sectioning , Then find the interval in order .

Code

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e5 + 10;

struct edge {
     int u, v, w; } edges[N << 1];

vector<int> g[N];

int pfa[N], dep[N], siz[N], son[N], top[N], dfn[N], rnk[N], ind;
int n, m;

void dfs1(int u, int fa){
    
    pfa[u] = fa, dep[u] = dep[fa] + 1, siz[u] = 1;
    for(auto &v : g[u]){
    
        if(v == fa) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int tp){
    
    dfn[u] = ++ind, rnk[tp] = 0, top[u] = tp;
    if(!son[u]) return;
    dfs2(son[u], tp);
    for(auto & v: g[u]){
    
        if(v == pfa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}


namespace SegmentTree{
    
    struct node{
    
        priority_queue<int> val, del;
        int top(){
    
            while(val.size() && del.size() && val.top() == del.top()) val.pop(), del.pop();
            return val.empty() ? -1 : val.top();
        }
    }tree[N << 2];

    #define ls rt << 1
    #define rs rt << 1 | 1
    #define lson ls, l , mid
    #define rson rs, mid + 1, r

    void update(int rt, int l, int r, int L, int R, int val){
    
        if(l >= L && r <= R){
    
            val > 0 ? tree[rt].val.emplace(val) : tree[rt].del.emplace(-val);
            return ;
        }
        int mid = l + r >> 1;
        if(mid >= L) update(lson, L, R, val);
        if(mid < R) update(rson, L, R, val);
    }

    int query(int rt, int l, int r, int pos){
    
        if(l == r) return tree[rt].top();
        int mid = l + r >> 1, ans = tree[rt].top();
        if(mid >= pos) ans = max(ans, query(lson, pos));
        else ans = max(ans, query(rson, pos));
        return ans;
    }
}

#define pii pair<int,int> 
#define fir first
#define sec second

void update(int u, int v, int w){
    
    vector<pii> interval;
    while(top[u] != top[v]){
    
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        interval.emplace_back(make_pair(dfn[top[u]], dfn[u]));
        u = pfa[top[u]];
    }
    interval.emplace_back(make_pair(min(dfn[u], dfn[v]), max(dfn[u], dfn[v])));
    sort(interval.begin(), interval.end());
    int modl = 1;
    for(auto & [l, r] : interval){
    
        int modr = l - 1;
        if(modl <= l - 1) SegmentTree::update(1, 1, n, modl, modr, w);
        modl = r + 1;
    }
    if(modl <= n) SegmentTree::update(1, 1, n, modl, n, w);
}


inline void solve(){
    
     cin >> n >> m;
    for(int i = 1; i <= n - 1; i++){
    
        int u, v; cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    for(int i = 1; i <= m; i++){
    
        int op; cin >> op;
        if(op == 0){
    
            cin >> edges[i].u >> edges[i].v >> edges[i].w;
            update(edges[i].u, edges[i].v, edges[i].w);
        }   
        else if(op == 1){
    
            int t; cin >> t;
            auto &[u ,v, w] = edges[t];
            update(u, v, -w);
        }
        else{
    
            int x; cin >> x;
            cout << SegmentTree::query(1, 1, n, dfn[x]) << endl;
        }
    }
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    solve();
    return 0;
}

[NECPC2022] F.Tree Path

Given a tree , contain $n$ Nodes and $k$ Strip weight path , Operation support is required ：

• Delete the smallest weighted path
• For a given node $x$, Output all without $x$ The minimum value in the weighted path of

The idea of following the question is similar , Maintain the complement of the nodes to be checked with the line segment tree , Note that the result here is the minimum .

Note that it must be discretized , otherwise $map$ More than one $log$ The explosion constant can't pass .

#include <bits/stdc++.h>
#pragma gcc optimize('O2')
//#define int long long
#define endl '\n'
using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

struct edge {
     int u, v, w; const bool operator< (const edge &x) {
     return w < x.w; }} edges[N];

vector<int> g[N];
int n, k, m;
int pfa[N], dep[N], siz[N], son[N], top[N], dfn[N], rnk[N], ind;
bool del[N];

void dfs1(int u, int fa){
    
    pfa[u] = fa, dep[u] = dep[fa] + 1, siz[u] = 1;
    for(auto &v : g[u]){
    
        if(v == fa) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int tp){
    
    dfn[u] = ++ind, rnk[tp] = 0, top[u] = tp;
    if(!son[u]) return;
    dfs2(son[u], tp);
    for(auto & v: g[u]){
    
        if(v == pfa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

namespace SegmentTree{
    
    struct node{
    
        priority_queue<int, vector<int>, greater<>> val;
        int top(){
    
            while(val.size() && del[val.top()]) val.pop();
            return val.empty() ? INF : val.top();
        }
    }tree[N << 2];

    #define lson rt << 1, l, mid
    #define rson rt << 1 | 1, mid + 1, r

    void update(int rt, int l, int r, int L, int R, int val){
    
        if(l >= L && r <= R){
    
            tree[rt].val.emplace(val);
            return;
        }
        int mid = l + r >> 1;
        if(mid >= L) update(lson, L, R, val);
        if(mid < R) update(rson, L, R, val);
    }

    int query(int rt, int l, int r, int pos){
    
        if(l == r) return tree[rt].top();
        int mid = l + r >> 1, ans = tree[rt].top();
        if(mid >= pos) ans = min(ans, query(lson, pos));
        else ans = min(ans, query(rson, pos));
        return ans;
    }
}

#define pii pair<int,int> 
#define fir first
#define sec second

void update(int u, int v, int w){
    
    vector<pii> interval;
    while(top[u] != top[v]){
    
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        interval.emplace_back(make_pair(dfn[top[u]], dfn[u]));
        u = pfa[top[u]];
    }
    interval.emplace_back(make_pair(min(dfn[u], dfn[v]), max(dfn[u], dfn[v])));
    sort(interval.begin(), interval.end());
    int modl = 1;
    for(auto & [l, r] : interval){
    
        int modr = l - 1;
        if(modl <= l - 1) SegmentTree::update(1, 1, n, modl, modr, w);
        modl = r + 1;
    }
    if(modl <= n) SegmentTree::update(1, 1, n, modl, n, w);
}

vector<int> v(1, -0x3f3f3f3f); 

inline void solve(){
    
    cin >> n >> k >> m;
    
    auto get = [&](int x) {
     return lower_bound(v.begin(), v.end(), x) - v.begin(); };
    auto dis = [&]() {
     sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); };

    for(int i = 1; i <= n - 1; i++){
    
        int u, v; cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    dfs1(1, 0), dfs2(1, 1);
    for(int i = 1; i <= k; i++){
    
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        v.emplace_back(edges[i].w);
    }
    dis();
    for(int i = 1; i <= k; i++){
    
        auto &[u, v, w] = edges[i];
        update(u ,v, get(w));
    }
    int min_pos = 1, last = 0;
    for(int i = 1; i <= m; i++){
    
        int op = 0; cin >> op;
        if(op == 1){
    
            int x; cin >> x, x = x ^ last;
            int ans = SegmentTree::query(1, 1, n, dfn[x]);
            last = (ans == INF ? -1 : v[ans]);
            cout << last << endl;
        }
        else{
    
            //auto &[u, v, w] = edges[min_pos++];
            del[min_pos++] = 1;
        }
    }
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    solve();
    return 0;
}