洛谷 P4092 [HEOI2016/TJOI2016]树 题解【树链剖分】/【并查集】/【模拟】

作者: wjyyy 分类: 并查集,,树链剖分,模拟,线段树,解题报告 发布时间: 2018-07-04 11:36

点击量:14

 

   虽然这题可以用树剖或并查集来做,不过裸奔是最快的。。。

 

题目描述

在2016年,佳媛姐姐刚刚学习了树,非常开心。现在他想解决这样一个问题:给定一颗有根树(根为1),有以下两种操作:

 

  1. 标记操作:对某个结点打上标记(在最开始,只有结点1有标记,其他结点均无标记,而且对于某个结点,可以打多次标记。)
  2. 询问操作:询问某个结点最近的一个打了标记的祖先(这个结点本身也算自己的祖先)

 

你能帮帮他吗?

 

输入输出格式

输入格式:

输入第一行两个正整数N和Q分别表示节点个数和操作次数

 

接下来N-1行,每行两个正整数u,v(1≤u,v≤n)表示u到v有一条有向边

 

接下来Q行,形如“opernum”oper为“C”时表示这是一个标记操作,oper为“Q”时表示这是一个询问操作对于每次询问操作。

 

输出格式:

输出一个正整数,表示结果

 

输入输出样例

输入样例#1:
5 5
1 2
1 3
2 4
2 5
Q 2
C 2
Q 2
Q 5
Q 3
输出样例#1:
1
2
2
1

说明

30%的数据,1 ≤ N, Q ≤ 1000

 

70%的数据,1 ≤ N, Q ≤ 10000

 

100%的数据,1 ≤ N, Q ≤ 100000

 

裸奔:

    dfs把这棵树构建出来,然后染色,询问直接沿着链找父亲。理论复杂度\(N^2\),实际复杂度\(O(N) \le O(?) \le O(N\log N)\)。下面贴代码。

 

树剖:

   首先我们看到这是一棵有根树,并且节点的改变可能会影响到它的子树,因此我们考虑树链剖分。不过这个树剖是一个阉割版的树剖,因为它只有子树查询,节省了60%的树剖过程。

 

   对于改变,我们只需要在线段树中添加一个判断,就是更新时对比,把答案改成深度较大的那一个。利用树剖的思想就可以做了。

 

并查集:

   想出这种做法的人真的是神奇%%%,用离线并查集的方式来做这道题。思路:我们把所有的询问存起来,接着把所有需要染色的全部染色。预处理并查集存最近染色祖先,在dfs里可以完成。当修改时,将这个点的cnt(染色次数)–,当cnt为0时,将它的最近染色祖先更新到它父亲的find。处理时细节比较多,最后记得正序输出即可,真坑

 

Code:时间实际复杂度从高到低排序

树剖

#include<cstdio>
#include<cstring>
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define Mid (t[k].l+t[k].r>>1)

struct edge
{
    int n,nxt;
    edge(int n,int nxt)
    {
        this->n=n;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[210000];
int head[101000],Cnt=-1;
void add(int from,int to)
{
    e[++Cnt]=edge(to,head[from]);
    head[from]=Cnt;
}
int d[101000],dfn[101000],cnt=0,over[101000];
int dmax(int x,int y)//判断深度大小并返回较深的一个
{
    return d[x]>d[y]?x:y;
}
void dfs(int x)
{
    dfn[x]=++cnt;
    for(int i=head[x];~i;i=e[i].nxt)
        if(!dfn[e[i].n])
        {
            d[e[i].n]=d[x]+1;
            dfs(e[i].n);
        }
    over[x]=cnt;
}
int n,m;
struct node
{
    int l,r,v,lazy;
    node(int l,int r,int v)
    {
        this->l=l;
        this->r=r;
        this->v=v;
        lazy=0;
    }
    node(int l,int r)
    {
        this->l=l;
        this->r=r;
        v=0;
        lazy=0;
    }
    node()
    {
        v=0;
        lazy=0;
    }
}t[410000];
void build(int k,int l,int r)
{
    if(l==r)
    {
        t[k]=node(l,r,1);
        return;
    }
    t[k]=node(l,r);
    build(ls,l,mid);
    build(rs,mid+1,r);
}
void pushdown(int k)
{
    if(t[k].l==t[k].r||!t[k].lazy)//lazy稍微改动一点
        return;
    t[ls].v=dmax(t[k].lazy,t[ls].v);
    t[ls].lazy=dmax(t[k].lazy,t[ls].lazy);
    t[rs].v=dmax(t[k].lazy,t[rs].v);
    t[rs].lazy=dmax(t[k].lazy,t[rs].lazy);
    t[k].lazy=0;
    return;
}
void change(int k,int l,int r,int x)
{
    if(l==t[k].l&&r==t[k].r)
    {
        t[k].lazy=dmax(t[k].lazy,x);
        t[k].v=dmax(t[k].lazy,x);
        return;
    }
    pushdown(k);
    if(r<=Mid)
        change(ls,l,r,x);
    else if(l>Mid)
        change(rs,l,r,x);
    else
    {
        change(ls,l,Mid,x);
        change(rs,Mid+1,r,x);
    }
}
int ask(int k,int x)
{
    pushdown(k);
    if(t[k].l==t[k].r)
        return t[k].v;
    if(x<=Mid)
        return ask(ls,x);
    else
        return ask(rs,x);
}
int main()
{
    d[0]=0;
    int u,v,k;
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    d[1]=1;
    dfs(1);
    build(1,1,n);
    char q;

    for(int i=1;i<=m;i++)
    {
        scanf("\n");
        q=getchar();
        scanf("%d",&k);
        if(q=='C')
            change(1,dfn[k],over[k],k);//只管子树,不用真正树剖
        else
            printf("%d\n",ask(1,dfn[k]));
    }
    return 0;
}

 

裸奔:O(N²)(事实证明这比树剖快 不知道luogu会不会出数据卡掉)

#include<cstdio>
#include<cstring>
struct edge
{
    int n,nxt;
    edge(int n,int nxt)
    {
        this->n=n;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[210000];
int head[101000],cnt=-1;
void add(int from,int to)
{
    e[++cnt]=edge(to,head[from]);
    head[from]=cnt;
}
int d[101000],fa[101000];
bool c[101000];
void dfs(int x)
{
    for(int i=head[x];~i;i=e[i].nxt)
    {
        if(!d[e[i].n])
        {
            d[e[i].n]=d[x]+1;
            fa[e[i].n]=x;//只用存个父亲就行了
            dfs(e[i].n);
        }
    }
}
int ask(int x)
{
    while(c[x]==0)
        x=fa[x];
    return x;
}
int main()
{
    memset(d,0,sizeof(d));
    memset(c,false,sizeof(c));
    memset(head,-1,sizeof(head));
    c[1]=true;
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    fa[1]=0;
    d[1]=1;
    dfs(1);
    char q;
    int k;
    for(int i=1;i<=m;i++)
    {
        scanf("\n%c%d",&q,&k);
        if(q=='C')
            c[k]=true;
        else
            printf("%d\n",ask(k));
    }
    return 0;
}

并查集:路径压缩理论O(N)维护,也是三种中最快的

#include<cstdio>
#include<cstring>
struct edge
{
    int n,nxt;
    edge(int n,int nxt)
    {
        this->n=n;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[210000];
int head[110000],Cnt=-1;
void add(int from,int to)
{
    e[++Cnt]=edge(to,head[from]);
    head[from]=Cnt;
}
struct ask
{
    char op;
    int num,ans;
    ask()
    {
        ans=0;
    }
}q[110000];
int s[110000];
int cnt[110000];
int fa[110000];
void dfs(int x)
{
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].n!=fa[x])
        {
            fa[e[i].n]=x;
            if(cnt[e[i].n])//注意这里的细节
                s[e[i].n]=e[i].n;
            else
                s[e[i].n]=s[x];
            dfs(e[i].n);
        }
}
int my_find(int x)
{
    if(s[x]==x)
        return x;
    return s[x]=my_find(s[x]);
}
int main()
{
    memset(head,-1,sizeof(head));
    memset(cnt,0,sizeof(cnt));
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        s[i]=i;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    s[n]=n;
    cnt[1]=1;
    for(int i=1;i<=m;i++)
    {
        scanf("\n%c%d",&q[i].op,&q[i].num);
        if(q[i].op=='C')
            cnt[q[i].num]++;//提前计算
    }
    fa[1]=1;
    cnt[1]++;
    dfs(1);//dfs处理
    for(int i=m;i>=1;i--)//倒着做
    {
        if(q[i].op=='Q')
            q[i].ans=my_find(q[i].num);
        else
        {
            cnt[q[i].num]--;
            if(!cnt[q[i].num])
                s[q[i].num]=fa[q[i].num];
        }
    }
    for(int i=1;i<=m;i++)//正着输出
        if(q[i].ans)
            printf("%d\n",q[i].ans);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */