SPOJ 2798 QTREE3 - Query on a tree again!

原oj题面

Time limit 2000 ms

Memory limit 1572864 kB

Code length Limit 50000 B

OS Linux

Language limit All except: ERL JS-RHINO NODEJS PERL6 VB.NET //c++呢？Java呢？Python呢？明明可以的

Source VNOI Marathon ‘08 - Round 6/DivA Problem Setter: Blue Mary

Author Fudan University Problem Setters

吐槽

两年后写的第二篇树剖，还是找了一两天的bug，最后发现，dfs1()里，if(v==t[u].fa) continue;被我写成了if(v==t[u].fa) return;。这样例里的树好像也不水了……而且我记得之前把建好的树输出，也没发现树上少了哪个点来着……不知道这个错误发生之前是不是有其他什么bug……

[HAOI2015]树上操作 这篇的操作3也是从根节点到给定点这一路的修改，我当年还觉得那时自己想的优化（因为一个点已经固定为根节点1，所以跳链时不用比较两条链顶端的深度，只需要下面那个点不停向上到达根就好）挺不错来着，结果现在发现只是那常规操作……

板子没有解题思路

源代码

#include<cstdio>
#include<cstring>
#include<algorithm>
int T;
int n,q;
//对于每个黑色点，线段树上的值对应点的新id
//对于每个白色点，线段树上的值为inf

struct Edge{
    int nxt,to;
}e[200010];
int cnt=1,head[100010];
void add(int u,int v)
{
    e[cnt]={head[u],v};
    head[u]=cnt++;
    e[cnt]={head[v],u};
    head[v]=cnt++;
}

struct Tree{
    int fa,dep,sz,wson;
    int id,top;
}t[100010];
void dfs1(int u,int fa)
{
    t[u].fa=fa;
    t[u].dep=t[fa].dep+1;
    t[u].sz=1;
    int maxn=-1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==fa) continue;//就是这里，之前写成return了
        dfs1(v,u);
        int temp=t[v].sz;
        t[u].sz+=temp;
        if(temp>maxn)
        {
            maxn=temp;
            t[u].wson=v;
        }
    }
}
int id=1;
int mp[100010];//用新的id查询老的id
void dfs2(int u,int top)
{
    t[u].top=top;
    mp[id]=u;
    t[u].id=id++;
    if(t[u].sz==1) return;
    dfs2(t[u].wson,top);
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==t[u].wson||v==t[u].fa) continue;
        dfs2(v,v);
    }
}

const int inf=0x7f7f7f7f;

struct Segtree{
    int l,r;//有点想改变码风，把这两个放到参数里去，以便和主席树统一
    int mn;
}s[400010];

void build(int x,int l,int r)
{
    s[x]={l,r,inf};
    if(l==r) return;
    int mid=l+r>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
}
void update(int x,int pos)
{
    if(s[x].l==s[x].r&&s[x].l==pos)
    {
        if(s[x].mn==inf)//染成黑色
            s[x].mn=pos;//赋值成新的id
        else//染成白色
            s[x].mn=inf;
        return;
    }
    int mid=s[x].l+s[x].r>>1;
    if(pos<=mid) update(x<<1,pos);
    else update(x<<1|1,pos);
    s[x].mn=std::min(s[x<<1].mn,s[x<<1|1].mn);
}
int que(int x,int r)//返回所求点新id
{
    if(l<=s[x].l&&s[x].r<=r)
        return s[x].mn;
    int mid=s[x].l+s[x].r>>1;
    int ans=inf;
    if(l<=mid) ans=std::min(ans,que(x<<1,r));
    if(r>mid) ans=std::min(ans,que(x<<1|1,r));
    return ans;
}

void opt0(int u)//改变u号点颜色
{
    update(1,t[u].id);
}
int opt1(int u)//返回1到u的第一个黑点的老id
{
    int ans=inf;
    while(u)
    {
        ans=std::min(ans,que(1,t[t[u].top].id,t[u].id));
        u=t[t[u].top].fa;
    }
    if(ans==inf) ans=-1;
    else ans=mp[ans];
    return ans;
}

int main()
{
    //freopen("test.in","r",stdin);
    scanf("%d%d",&n,&q);
    for(int i=1,u,v;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    while(q--)
    {
        int opt,u;
        scanf("%d%d",&opt,&u);
        if(opt) printf("%dn",opt1(u));
        else opt0(u);
    }
    return 0;
}