P3250 [HNOI2016] 网络 + [NECPC2022] F.Tree Path 树剖+线段树维护堆

两道题思路非常像，因此集中记录一下思路和做法

P3250 [HNOI2016] 网络 题目分析

给定一棵有 n n n个节点的树, 有 m m m次如下操作:

0 a b c 表示在 ( a , b ) (a, b) (a,b)的最短路径上增加一条重要度为 c c c的边.

1 t 表示删除第 t t t次操作所增加的边

2 x 表示节点 x x x出现故障. 此时需要回答, 所有不经过 x x x节点的边中最大的重要度.

首先将边权点权化，也就是树上问题序列化，然后利用用线段树维护待查点的补集。由于线段树节点维护序列最大值，因此将节点开成大根堆，然后每个节点记录不经过该节点的路径中的最大权，以及删除的权值。

对于每个增边操作，树剖LCA求出路径所占的全部区间，然后对其补集进行修改。补集可以先对树剖求出的区间排序，然后按顺序找间隔即可。

Code

#include 
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e5 + 10;

struct edge { int u, v, w; } edges[N  m;
    for(int i = 1; i > u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    for(int i = 1; i > 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  v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    dfs1(1, 0), dfs2(1, 1);
    for(int i = 1; i > edges[i].u >> edges[i].v >> edges[i].w;
        v.emplace_back(edges[i].w);
    }
    dis();
    for(int i = 1; i  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