题意：一棵树，支持添加一条u到v权值为k的路径，删除之前的一条路径，询问不经过点x的路径的最大权值

---

考虑二分

整体二分最大权值，如果\(k \in [mid+1,r]\)中的路径有不经过x的，那么这个询问的答案在\([mid+1,r]\)中

链修改，点查询\(\rightarrow\)点修改，子树查询，方法是\(u,v +1\ ;\ lca,fa[lca] -1\)

用树状数组就可以完成

这里的整体二分不需要对每个询问保存当前贡献，因为每次只需要考虑一段的贡献

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define fir first#define sec secondconst int N=2e5+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}    return x*f;}int n, Q, id[N], mp[N], t1[N], t2[N], ans[N];struct meow{int op, u, v, k, t, x;} q[N];struct edge{int v, ne;}e[N-1];int cnt=1, h[N];inline void ins(int u, int v) {    e[++cnt]=(edge){v, h[u]}; h[u]=cnt;    e[++cnt]=(edge){u, h[v]}; h[v]=cnt;}namespace tr {    pair
         
           dfn[N]; int fa[N], deep[N], dfc, tot, pos[N], f[N<<1][18]; void dfs(int u) { dfn[u].fir = ++dfc; f[++tot][0] = u; pos[u] = tot; for(int i=h[u];i;i=e[i].ne) if(e[i].v != fa[u]) { fa[e[i].v] = u; deep[e[i].v] = deep[u]+1; dfs(e[i].v); f[++tot][0] = u; } dfn[u].sec = dfc; } int log[N]; inline int min(int x, int y) {return deep[x] < deep[y] ? x : y;} void init() { dfs(1); //for(int i=1; i<=tot; i++) printf("%d ", f[i][0]); puts(""); for(int j=1; j<=17; j++) for(int i=1; i+(1<
          
           <=tot; i++) f[i][j] = min(f[i][j-1], f[i+(1<<(j-1))][j-1]);// printf("f %d %d %d\n",i,j,f[i][j]); log[1]=0; for(int i=2; i<=tot; i++) log[i] = log[i>>1]+1; } inline int lca(int x, int y) { x = pos[x], y = pos[y]; if(x>y) swap(x, y); int t = log[y-x+1]; return min(f[x][t], f[y-(1<
           
            >1, p1=0, p2=0; //printf("mid %d\n", mid); bit::ini(); int now=0; for(int i=ql; i<=qr; i++) { int _=i; i=id[i]; //printf("i-------- %d %d %d\n",_,i, q[i].op); if(q[i].op == 1) { //printf("k %d\n", q[i].k); if(q[i].k > mid) cha(i, 1), now++, t2[++p2] = i; else t1[++p1] = i; } else if(q[i].op == 2) { if(q[ q[i].t ].k > mid) cha(q[i].t, -1), now--, t2[++p2] = i; else t1[++p1] = i; } else { int x = q[i].x, cnt = sum(dfn[x].fir, dfn[x].sec); //printf("hi que %d %d %d\n", x, cnt, now); if(cnt < now) t2[++p2] = i; else t1[++p1] = i; } i=_; } for(int i=1; i<=p1; i++) id[ql+i-1] = t1[i]; for(int i=1; i<=p2; i++) id[ql+p1+i-1] = t2[i]; cdq(l, mid, ql, ql+p1-1); cdq(mid+1, r, ql+p1, qr);}int main() { //freopen("in", "r", stdin); freopen("network_tenderRun.in", "r", stdin); freopen("network_tenderRun.out", "w", stdout); n=read(); Q=read(); for(int i=1; i