M_sea

洛谷3250 [HNOI2016]网络
LuoguBZOJ分析整体二分。对于每个询问,查询经过它的路径,然后对应地丢到左边或右边。对于每个修改,判断它的权...
扫描右侧二维码阅读全文
25
2019/02

洛谷3250 [HNOI2016]网络

Luogu

BZOJ

分析

整体二分。

对于每个询问,查询经过它的路径,然后对应地丢到左边或右边。

对于每个修改,判断它的权值是否大于 $mid$ ,如果是就修改并丢到右边,否则丢到左边。

可以用树状数组来维护子树权值和,每次用树上差分的方式来修改。

具体实现和细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,m;

//邻接表
struct Edge { int v,nxt; } e[N<<1];
int head[N];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

//询问
struct Query { int op,ans,id,x; } q[N],lq[N],rq[N];
int a[N],b[N],v[N];
bool operator <(Query a,Query b) { return a.id<b.id; }

//树剖
int fa[N],sz[N],dep[N],hson[N],top[N];
int st[N],ed[N],dfs_clock=0;

inline void dfs1(int u,int f) {
    fa[u]=f,sz[u]=1,dep[u]=dep[f]+1,st[u]=++dfs_clock;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        dfs1(v,u); sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
    ed[u]=dfs_clock;
}

inline void dfs2(int u,int anc) {
    top[u]=anc;
    if (hson[u]) dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v!=fa[u]&&v!=hson[u]) dfs2(v,v);
    }
}

//求LCA
inline int LCA(int u,int v) {
    int x=top[u],y=top[v];
    while (x!=y) {
        if (dep[x]>dep[y]) u=fa[x],x=top[u];
        else v=fa[y],y=top[v];
    }
    return dep[u]<dep[v]?u:v;
}

//树状数组
int c[N],mx;

#define lowbit(x) (x&-x)
inline void add(int x,int y) {
    for (;x<=n;x+=lowbit(x)) c[x]+=y;
}
inline int sum(int x) {
    int ans=0;
    for (;x;x-=lowbit(x)) ans+=c[x];
    return ans;
}

//树上差分
inline void modify(int u,int v,int w) {
    int t=LCA(u,v);
    add(st[u],w),add(st[v],w),add(st[t],-w);
    if (fa[t]) add(st[fa[t]],-w);
}

//整体二分
inline void solve(int lval,int rval,int L,int R) {
    if (L>R) return;
    if (lval==rval) {
        for (re int i=L;i<=R;++i)
            if (q[i].op==2) q[i].ans=lval;
        return;
    }
    int mid=(lval+rval)>>1,lt=0,rt=0,path=0;
    for (re int i=L;i<=R;++i) {
        if (q[i].op==2) {
            if (sum(ed[q[i].x])-sum(st[q[i].x]-1)==path) lq[++lt]=q[i];
            else rq[++rt]=q[i];
        } else {
            if (v[q[i].x]<=mid) lq[++lt]=q[i];
            else {
                int v=q[i].op?-1:1;
                path+=v; modify(a[q[i].x],b[q[i].x],v);
                rq[++rt]=q[i];
            }
        }
    }
    for (re int i=L;i<=R;++i) {
        if (q[i].op==2||v[q[i].x]<=mid) continue;
        int v=q[i].op?1:-1;
        modify(a[q[i].x],b[q[i].x],v);
    }
    for (re int i=1;i<=lt;++i) q[L+i-1]=lq[i];
    for (re int i=1;i<=rt;++i) q[L+lt+i-1]=rq[i];
    solve(lval,mid,L,L+lt-1); solve(mid+1,rval,L+lt,R);
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v); addEdge(v,u);
    }
    dfs1(1,0); dfs2(1,1);
    for (re int i=1;i<=m;++i) {
        q[i].op=read(),q[i].id=i;
        if (!q[i].op) {
            a[i]=read(),b[i]=read(),v[i]=read(),q[i].x=i;
            mx=max(mx,v[i]);
        }
        else q[i].x=read();
    }
    solve(-1,mx,1,m); sort(q+1,q+m+1);
    for (re int i=1;i<=m;++i)
        if (q[i].op==2) printf("%d\n",q[i].ans);
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 00 PM

发表评论