DLKKILL

DLKKILL's world

HDU - 3887 - Counting Offspring(DFS序+线段树)

题目链接:HDU – 3887

题目大意:问你对于每个节点,它的子树上标号比它小的点有多少个 

题目分析:

利用DFS序建立一个初始节点值都为0的线段树。

每次先查询值,然后讲该点加入到线段树里面去。

给出代码:

#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e5+10;
int lx[maxn],rx[maxn];
vector<int> g[maxn];
int sum[maxn<<2];
int order=0;
void init()
{
    order=0;
    for(int i=0;i<maxn;i++)
        g[i].clear();
    memset(lx,0,sizeof(lx));
    memset(rx,0,sizeof(rx));
    memset(sum,0,sizeof(sum));
}
void dfs(int u,int f)
{
    lx[u]=++order;
    for(int i=0; i<g[u].size(); i++)
    {
        int v=g[u][i];
        if(v==f)
            continue;
        dfs(v,u);
    }
    rx[u]=order;
}
void push_node(int root)
{
    sum[root]=sum[root<<1]+sum[root<<1|1];
}
void build(int l,int r,int node)
{
    if(l==r)
    {
        sum[node]=0;
        return;
    }
    sum[node]=0;
    int mid=(r+l)>>1;
    build(l,mid,node<<1);
    build(mid+1,r,node<<1|1);
    return;
}
void change(int l,int r,int node,int pos,int d)
{
    if(l==r)
    {
        sum[node]+=d;
        return;
    }
    int mid=(r+l)>>1;
    if(pos<=mid)
        change(l,mid,node<<1,pos,d);
    else
        change(mid+1,r,node<<1|1,pos,d);
    push_node(node);
    return;
}
int query(int l,int r,int L,int R,int node)
{
    if(L<=l&&r<=R)
        return sum[node];
    int mid=(r+l)>>1;
    int res=0;
    if(L<=mid)
        res+=query(l,mid,L,R,node<<1);
    if(R>mid)
        res+=query(mid+1,r,L,R,node<<1|1);
    return res;
}
int n,p;
int main()
{
    while(cin>>n>>p&&p)
    {
        init();
        for(int i=0; i<n-1; i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            g[a].push_back(b);
            g[b].push_back(a);
        }
        dfs(p,-1);
        build(1,n,1);
        for(int i=1; i<=n; i++)
        {
            if(i!=1)
                cout<<" ";
            // cout<<lx[i]<<" "<<rx[i]<<endl;
            // cout<<"********"<<"  "<<i<<endl;
            int t=query(1,n,lx[i],rx[i],1);
            printf("%d",t);
            // cout<<"********"<<"  "<<i<<endl;
            change(1,n,1,lx[i],1);
            //   cout<<"********"<<"  "<<i<<endl;
        }
        cout<<endl;
    }
    return 0;
}

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注