关于时间复杂度

/*
 * @Author: china_banana
 * @Date: 2026-02-20 09:57:49
 * @LastEditTime: 2026-02-20 11:27:34
 */
#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define V 262145 
#define M 200005

int n,m;

vector<int>G[N];
int dep[N],siz[N],wson[N],fa[N];
void dfs1(int u,int fath)
{
    siz[u]=1;
    fa[u]=fath;
    dep[u]=dep[fath]+1;

    for(auto v:G[u])
    {   
        if(v==fath) continue;
        else {
            dfs1(v,u);
            siz[u]+=siz[v];
            if(siz[v]>siz[wson[u]]) wson[u]=v;
        }
    }
}

int dfn[N],id,top[N];
void dfs2(int u,int ltop)
{
    dfn[u]=++id;
    top[u]=ltop;

    if(wson[u]) dfs2(wson[u],ltop);
    for(auto v:G[u])
    {
        if(v==wson[u]||v==fa[u]) continue;
        else dfs2(v,v);
    }
}

namespace seg
{
    struct node {
        int l,r;
        priority_queue<int>add,del;

    }tr[V];

    #define mid ((tr[root].l+tr[root].r)>>1)
    #define ls(x) x<<1
    #define rs(x) x<<1|1

    void build(int root,int l,int r)
    {
        tr[root].l=l,tr[root].r=r;
        tr[root].add.push(-1);
        if(l==r) return;
        else 
        {
            build(ls(root),l,mid);
            build(rs(root),mid+1,r);
        }
    }

    void update(int root,int ql,int qr,int type,int v)
    {
        if(ql<=tr[root].l&&qr>=tr[root].r)
        {
            if(type==0) tr[root].add.push(v);
            else tr[root].del.push(v);
        }else 
        {
            if(ql<=mid) update(ls(root),ql,qr,type,v);
            if(qr>mid) update(rs(root),ql,qr,type,v);
        }
    }

    void change(int root)
    {
        while(!tr[root].add.empty()&&!tr[root].del.empty()&&tr[root].add.top()==tr[root].del.top())
        {
            tr[root].add.pop();
            tr[root].del.pop();
        }
    } 

    int query(int root,int x)
    {
        change(root);
        if(tr[root].l==tr[root].r) return tr[root].add.top();
        else {
            int v=tr[root].add.top();
            if(x<=mid) return max(query(ls(root),x),v);
            else return max(query(rs(root),x),v);
        }
    }
}

pair<int,int>line[N];
using namespace seg;

void update_path(int a,int b,int v,int type)
{
    int len=0;
    while(top[a]!=top[b])
    {
        if(dep[top[a]]<dep[top[b]]) swap(a,b);
        line[++len]={dfn[top[a]],dfn[a]},a=fa[top[a]];
    }
    if(dep[a]>dep[b]) swap(a,b);
    line[++len]={dfn[a],dfn[b]};
    sort(line+1,line+len+1);
    for(int i=1;i<=len;++i)
        if(line[i-1].second+1<=line[i].first-1) update(1,line[i-1].second+1,line[i].first-1,type,v); 
    if(line[len].second+1<=n) update(1,line[len].second+1,n,type,v);
}


struct question {
    int a,b,v;
}ques[M];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>m;

    for(int i=1;i<n;++i)
    {
        int u,v;cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);

    for(int i=1;i<=m;++i)
    {
        int type;cin>>type;
        if(type==0) {
            int a,b,v;cin>>a>>b>>v;
            update_path(a,b,v,type);
            ques[i]={a,b,v};
        }else if(type==1) {
            int t;cin>>t;
            int a,b,v;
            a=ques[t].a,b=ques[t].b,v=ques[t].v;
            update_path(a,b,v,type);
        }else {
            int x;cin>>x;
            cout<<query(1,dfn[x])<<"\n";
        }
    }

    return 0;
}
```cpp