【BZOJ4285】使者

2016.03.22 15:01 Tue | 42次阅读 | 旧日oi | 固定链接 | 源码

题解

树套树

懒的写cdq了,直接树套树一发过去得了,正好第二层主席树能套上个题代码……
先搞出dfs序,如果u不是v的祖先,那么可行的跳跃点就是u的子树到v的子树之间的,也就是在dfs序中的两段区间构成的一个矩形里,如果是祖先的话,找到u到v的路径上离u最近的那个点,那么答案除了这个点的子树以外的部分到v的子树中的跳跃点个数……总之是个二维数点,细节我就不说了……

mycode

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int n,m,Q,num;
int h[N],tp=1;
struct edge{int to,next,val;}e[N<<1];
void ae(int u,int v,int w=0){e[++tp].to=v;e[tp].next=h[u];e[tp].val=w;h[u]=tp;}
int st[N],ed[N],dep[N],tim;
int fa[N][18];
void dfs(int u,int f)
{
    st[u]=++tim;
    for(int i=1;i<=17;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=h[u];i;i=e[i].next)
    if(e[i].to!=f) 
    {
        dep[e[i].to]=dep[u]+1;
        fa[e[i].to][0]=u;
        dfs(e[i].to,u);
    }
    ed[u]=tim;
}
int ls[N*200],rs[N*200],val[N*200],root[N<<2];
void insert2(int &x,int l,int r,int p,int v)
{
    if(!x) x=++num;
    val[x]+=v;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(p<=mid) insert2(ls[x],l,mid,p,v);
    else insert2(rs[x],mid+1,r,p,v);
}
int query2(int x,int l,int r,int L,int R)
{
    if(!x) return 0;
    if(L==l&&R==r) return val[x];
    int mid=(l+r)>>1;
    if(R<=mid) return query2(ls[x],l,mid,L,R);
    else if(L>mid) return query2(rs[x],mid+1,r,L,R);
    else return query2(ls[x],l,mid,L,mid)+query2(rs[x],mid+1,r,mid+1,R);
}
int query1(int l,int r,int rt,int L,int R,int ll,int rr)
{
    if(L==l&&R==r) return query2(root[rt],1,n,ll,rr);
    int mid=(l+r)>>1;
    if(R<=mid) return query1(lson,L,R,ll,rr);
    else if(L>mid) return query1(rson,L,R,ll,rr);
    else return query1(lson,L,mid,ll,rr)+query1(rson,mid+1,R,ll,rr);
}
void insert1(int l,int r,int rt,int p,int y,int v)
{
    insert2(root[rt],1,n,y,v);
    if(l==r) return;
    int mid=(l+r)>>1;
    if(p<=mid) insert1(lson,p,y,v);
    else insert1(rson,p,y,v);
}
void insert0(int x,int y,int v)
{
    if(st[x]>st[y]) swap(x,y);
    insert1(1,n,1,st[x],st[y],v);
}
int getpos(int x,int y)
{
    int t=dep[y]-dep[x]-1;
    for(int i=0;i<18;i++) 
    if(t&(1<<i)) y=fa[y][i];
    return y;
}
int query0(int x,int y)
{
    if(st[x]>st[y]) swap(x,y);
    if(ed[x]>=ed[y])
    {
        x=getpos(x,y);
        return query1(1,n,1,1,st[x]-1,st[y],ed[y])+query1(1,n,1,st[y],ed[y],ed[x]+1,n);
    }
    else return query1(1,n,1,st[x],ed[x],st[y],ed[y]);
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    cin>>n;
    for(int u,v,i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        ae(u,v);ae(v,u);
    }
    cin>>m;
    dfs(1,0);
    for(int x,y,i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        insert0(x,y,1);
    }
    cin>>Q;
    for(int op,x,y,i=1;i<=Q;i++)
    {
        scanf("%d%d%d",&op,&x,&y);
        if(op==1) insert0(x,y,1);
        else if(op==2) insert0(x,y,-1);
        else printf("%d\n",query0(x,y));
    }
}