【题解】「HNOI2016」网络 整体二分/二分+树状数组+树上差分 loj2049 —Qiuly

对于一个询问，考虑二分其答案，对于当前的 $mid$ ，如果这个时刻存在的所有路径中所有权值 $>mid$ 的路径全部经过了当前询问的点 $x$ ，那么 $x$ 的答案只能在 $(l,mid)$ 中找，否则，如果存在权值 $>mid$ 且没有覆盖到 $x$ 的路径，那么 $x$ 的答案一定存在于 $(mid+1,r)$ 之间了，毕竟对于权值在 $(l,mid)$ 之间的路径来说，这些路径更优。

关于路径是否覆盖 $x$ ，这个可以用树上差分 $+$树状数组解决。

时间复杂度貌似是 $O(mlog^2n)$ 。（不会算…

不知道上面的是不是假的于是搞个整体二分算了吧……

Code：

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define freopen(A) {freopen(A".in","r",stdin);freopen(A".out","w",stdout);}

const int N=1e5+2;
const int LogN=22;
const int M=2e5+2;
int n,m,tot,cnt,c[N],h[M],head[N],ans[M];
struct Edge {int nxt,to;} G[N<<1];
struct Query {int t,u,v,w,id,lca;bool y;} s[M],q1[M],q2[M];

inline void add(int u,int v) {
    G[++cnt]=(Edge){head[u],v},head[u]=cnt;
    G[++cnt]=(Edge){head[v],u},head[v]=cnt;
}

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

namespace Lca {
    int dep[N],dfn[N],siz[N],fa[N][LogN+4];
    void dfs(int u,int f) {
        fa[u][0]=f,dep[u]=dep[f]+1,dfn[u]=++dfn[0],siz[u]=1;
        for(int i=1;i<=LogN;++i) 
            fa[u][i]=fa[fa[u][i-1]][i-1];
        for(int i=head[u];i;i=G[i].nxt) 
            if(G[i].to!=f) dfs(G[i].to,u),siz[u]+=siz[G[i].to];
    }
    int lca(int x,int y) {
        if(dep[x]<dep[y]) swap(x,y);
        for(int i=LogN;i>=0;--i) 
            if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
        if(x==y) return x;
        for(int i=LogN;i>=0;--i) 
            if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
        return fa[x][0];
    }
}using namespace Lca;

int lowbit(int x) {return (x&(-x));}
void upd(int x,int y) {for(int i=x;i<=n;i+=lowbit(i)) c[i]+=y;}
int sum(int x) {int res=0;for(int i=x;i;i-=lowbit(i)) res+=c[i];return res;}
void solve(int l,int r,int L,int R) {
    if(L>R) return;
    for(int i=L;i<=R;++i) if(s[i].t==2) goto _continue;
    return;_continue:;
    if(l==r) {
        for(int i=L;i<=R;++i) if(s[i].id) ans[s[i].id]=l;
        return;
    }
    int mid=(l+r)>>1,res=0,tot1=0,tot2=0;
    for(int i=L;i<=R;++i) {
        if(s[i].t==2) {
            if(sum(dfn[s[i].u]+siz[s[i].u]-1)-sum(dfn[s[i].u]-1)==res) q2[++tot2]=s[i];
            else q1[++tot1]=s[i];
        } else {
            if(s[i].w>mid) q2[++tot2]=s[i];
            else {
                int w=s[i].t?-1:1;res+=w;
                upd(dfn[s[i].u],w),upd(dfn[s[i].v],w),
                upd(dfn[s[i].lca],-w);if(fa[s[i].lca][0]) upd(dfn[fa[s[i].lca][0]],-w);
                q1[++tot1]=s[i];
            }
        }
    }
    for(int i=1;i<=tot1;++i) s[L+i-1]=q1[i];
    for(int i=1;i<=tot2;++i) s[L+tot1+i-1]=q2[i];
    for(int i=L;i<=R;++i) 
        if(s[i].t!=2&&s[i].w<=mid&&s[i].y) {
            int w=s[i].t?1:-1;
            upd(dfn[s[i].u],w),upd(dfn[s[i].v],w),
            upd(dfn[s[i].lca],-w);if(fa[s[i].lca][0]) upd(dfn[fa[s[i].lca][0]],-w);
        }
    solve(l,mid,L,L+tot1-1),solve(mid+1,r,L+tot1,R);
}

int main() {
    freopen("2049");
    IN(n),IN(m);
    for(int i=1,u,v;i<n;++i) IN(u),IN(v),add(u,v);
    dfs(1,0);
    for(int i=1,t;i<=m;++i) {
        IN(s[i].t);
        if(!s[i].t) {
            IN(s[i].u),IN(s[i].v),IN(s[i].w),h[++tot]=-s[i].w;
            s[i].lca=lca(s[i].u,s[i].v),s[i].y=1;
        }
        else if(s[i].t==1) IN(t),s[i]=s[t],s[i].t=1,s[i].y=s[t].y=0;
        else IN(s[i].u),s[i].id=++ans[0];
    }
    h[++tot]=1;
    sort(h+1,h+1+tot),tot=unique(h+1,h+1+tot)-h-1;
    for(int i=1;i<=m;++i)
        if(s[i].t!=2) s[i].w=lower_bound(h+1,h+1+tot,-s[i].w)-h;
    for(int i=1;i<=tot;++i) h[i]=-h[i];
    solve(1,tot,1,m);
    for(int i=1;i<=ans[0];++i) printf("%d\n",h[ans[i]]);
    return 0;
}