bzoj4538[HNOI2016]网络

首先容易想到一个log^2的做法，就是这个答案是可以二分的，那么使用线段树套线段树，第一个线段树是权值线段树，第二个线段树记这些权值的路径在每个点的经过次数。那么询问就是在权值线段树上看右儿子的那个点是不是被右儿子的所有路径都覆盖到了，即那个点的经过次数等于右儿子的路径数，如果是那么就往左儿子走，否则往右儿子走。
显然这个空间复杂度不能接受，而且效率令人堪忧，于是用整体二分加bit即可，思路差不多。空间复杂度和常数都小很多，时间复杂度仍是\(O(nlog^2n)\)的，貌似在各大oj上都是前几名2333。

#include
#include
#include
#include
#include
#include
#include
#include
#define P puts("lala")
#define cp cerr<<"lala"<'9'){if(ch=='-')g=-1; ch=getchar();}
    while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+(ch^48),ch=getchar();
    return re*g;
}
typedef long long ll;
typedef pair pii;

const int N=100050;
const int M=200050;
int head[N],cnt=0;
struct node
{
    int to,next;
}e[N<<1];
inline void add(int x,int y)
{
    e[++cnt]=(node){y,head[x]};head[x]=cnt;
    e[++cnt]=(node){x,head[y]};head[y]=cnt;
}
int dfn[N],efn[N],clk=0,f[N][23],dep[N];
void dfs(int u,int fa,int d)
{
    dfn[u]=++clk; f[u][0]=fa; dep[u]=d;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u,d+1);
    }
    efn[u]=clk;
}
int lca(int x,int y)
{
    if(dep[x]=0;--i) if(d&1<=0;--i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}

struct qwe
{
    int t,x,y,z,v,k;
    qwe(int t=0,int x=0,int y=0,int z=0,int v=0,int k=0):t(t),x(x),y(y),z(z),v(v),k(k){ }
};
qwe upd[M],ask[M],A[M],B[M];
bool cmp1(qwe a,qwe b) {return a.t>1,n1=0,n2=0;
    for(int i=ul;i<=ur;++i)
        if(upd[i].v<=mid) A[++n1]=upd[i];
        else B[++n2]=upd[i];
    int umid=ul+n1-1;
    for(int i=ul;i<=umid;++i) upd[i]=A[i-ul+1];
    for(int i=umid+1;i<=ur;++i) upd[i]=B[i-umid];

    n1=0; n2=0;
    int p1=umid+1,now=0;
    for(int i=ql;i<=qr;++i)
    {
        while(p1<=ur&&upd[p1].t