【bzoj1095】[ZJOI2007]Hide 捉迷藏

2015.06.11 11:30 Thu | 14次阅读 | 旧日oi | 固定链接 | 源码

题目大意:给定一颗树,有黑点和白点,每次可以更改任意一个点的颜色,询问当前距离最远的两个黑点的距离。
题解
这题和spoj qtree4很像,是那个的简化版,这道题可以用什么括号序列解决,但是那个就不行了。不过这道题我还是用的和那道题一样的边分治。
关于边分治的介绍可以去看2009集训队漆子超的论文。
首先要加点来保证边分治的log级复杂度。然后每次选择一条边,把这条边连的两个节点分别树形dp,求出每个黑点到当前点的距离,扔到一个堆里,然后把这条边看做一个点,把堆关联到这个点上。这个点左右儿子分别是两颗子树选出来的边,递归处理就行了。
修改成白色的时候把这个点的距离在从这个点到根的路径中的每个点对应的堆中修改成-inf就行了,改回黑色再换回来。每次修改维护出每个节点的最大值。
询问就是O(1)的了。
这题的确很难写啊……自己写了俩小时没写明白,跟着标程的思路写的……

我的程序

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define N 200005
#define M 20
#define inf 0x3f3f3f3f
int n,Q,nn,now,cnt,root;
int q[N],front,tail;
int fa[N],val[N],siz[N],s[N],last[N],path[N],leaf[N];
int heap[N*M];
int dis[N][M],pos[N][M],dist[N][M];
struct edge
{
    int to,next,val,cut;
}e[N<<1];
int h[N],tp=1;
void ae(int u,int v,int w)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    e[tp].val=w;
    h[u]=tp;
}
int vis[N];
struct Tree{
    int st,ed,fa,ans,cost,l,r,dep;
}tree[N<<1];
void jiadian()
{
    q[front=tail=1]=1;vis[1]=1;
    while(front<=tail)
    {
        int u=q[front++];
        for(int v,i=h[u];e[i].to;i=e[i].next)
        if(!vis[v=e[i].to])
        {
            fa[v]=u;
            vis[v]=1;
            q[++tail]=v;
            val[v]=e[i].val;
        }
    }
    memset(h,0,sizeof(h));tp=1;
    for(int i=2;i<=n;i++) siz[fa[q[i]]]++;
    front=2;
    while(front<=tail)
    {
        int u=q[front++];
        if(front<=tail&&fa[u]==fa[q[front]])
        {
            n++;
            ae(u,n,val[u]);ae(n,u,val[u]);
            ae(q[front],n,val[q[front]]);ae(n,q[front],val[q[front]]);
            q[++tail]=n;front++;fa[n]=fa[u];siz[fa[u]]--;
        }
        else
        {
            if(siz[fa[u]]==1){ae(u,fa[u],val[u]);ae(fa[u],u,val[u]);}
            else q[++tail]=u;
        }
    }
}
void swp(int x,int y,int dep)
{
    swap(pos[heap[x]][dep],pos[heap[y]][dep]);
    swap(heap[x],heap[y]);
}
void up(int l,int w,int dep)
{
    w=w-l+1;l--;
    while(w>1&&dis[heap[l+w]][dep]>dis[heap[l+w/2]][dep])
    {
        swp(l+w,l+w/2,dep);
        w/=2;
    }
}
void down(int l,int w,int r,int dep)
{
    w=w-l+1;r=r-l+1;l--;
    int t=2*w;
    while(t<=r)
    {
        if(t<r&&dis[heap[l+t+1]][dep]>dis[heap[l+t]][dep]) t++;
        if(dis[heap[l+t]][dep]>dis[heap[w+l]][dep])
        {
            swp(l+t,l+w,dep);
            w=t;t=2*w;
        }
        else break;
    }
}
void dp(int u,int dep,int x)
{
    q[front=tail=1]=u;
    while(front<=tail)
    {
        u=q[front++];vis[u]=dep;s[u]=1;dist[u][dep]=-inf;
        for(int v,i=h[u];e[i].to;i=e[i].next)
        if(!e[i].cut&&vis[v=e[i].to]!=dep)
        {
            q[++tail]=v;
            dis[v][dep]=dis[u][dep]+e[i].val;
            path[v]=i;last[v]=u;
        }
        if(u>nn) dis[u][dep]=-inf;
        heap[++now]=u;
        pos[u][dep]=now;
        up(tree[x].st,now,dep);
        down(tree[x].st,now,tree[x].ed,dep);
    }
    for(int i=tail;i>1;i--) s[last[q[i]]]+=s[q[i]];
}
int get_edge(int x)
{
    int minn=inf,ans,sum=tree[x].ed-tree[x].st+1;
    if(sum==1) return -1;
    for(int i=tree[x].st;i<=tree[x].ed;i++)
    if(minn>abs(2*s[heap[i]]-sum))
    {
        minn=abs(2*s[heap[i]]-sum);
        ans=path[heap[i]];
    }
    return ans;
}
void update(int x)
{
    tree[x].ans=dis[heap[tree[tree[x].l].st]][tree[x].dep+1]+tree[x].cost+
                dis[heap[tree[tree[x].r].st]][tree[x].dep+1];
    tree[x].ans=max(tree[x].ans,max(tree[tree[x].l].ans,tree[tree[x].r].ans));
}
void bianfenzhi(int &x,int u,int dep,int f)
{
    x=++cnt;tree[x].fa=f;
    tree[x].dep=dep;tree[x].st=now+1;
    //cout<<tree[x].st<<" ";
    dp(u,dep,x);tree[x].ed=now;
    //cout<<tree[x].ed<<endl;
    int k=get_edge(x);
    if(k==-1){tree[x].ans=0;leaf[u]=x;return;}
    tree[x].cost=e[k].val;
    e[k].cut=e[k^1].cut=1;
    bianfenzhi(tree[x].l,e[k].to,dep+1,x);
    bianfenzhi(tree[x].r,e[k^1].to,dep+1,x);
    update(x);
}
void change(int x)
{
    for(int i=leaf[x];i;i=tree[i].fa)
    {
        int dep=tree[i].dep;
        swap(dis[x][dep],dist[x][dep]);
        up(tree[i].st,pos[x][dep],dep);
        down(tree[i].st,pos[x][dep],tree[i].ed,dep);
        if(i==leaf[x]) tree[i].ans=dis[x][dep];
        else update(i);
    }
}
int main()
{
    cin>>n;nn=n;
    for(int u,v,i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        ae(u,v,1);ae(v,u,1);
    }
    jiadian();
    memset(vis,-1,sizeof(vis));
    bianfenzhi(root,1,0,0);
    cin>>Q;char s[2];int x;
    while(Q--)
    {
        scanf("%s",s);
        if(s[0]=='G') printf("%d\n",tree[root].ans>=0?tree[root].ans:-1);
        else scanf("%d",&x),change(x);
    }
}```