BZOJ1782[USACO 2010 Feb Gold 3.Slowing down]——dfs+treap

题目描述

每天Farmer John的N头奶牛(1 <= N <= 100000，编号1…N)从粮仓走向他的自己的牧场。牧场构成了一棵树，粮仓在1号牧场。恰好有N-1条道路直接连接着牧场，使得牧场之间都恰好有一条路径相连。第i条路连接着A_i，B_i，(1 <= A_i <= N; 1 <= B_i <= N)。奶牛们每人有一个私人牧场P_i (1 <= P_i <= N)。粮仓的门每次只能让一只奶牛离开。耐心的奶牛们会等到他们的前面的朋友们到达了自己的私人牧场后才离开。首先奶牛1离开，前往P_1；然后是奶牛2，以此类推。当奶牛i走向牧场P_i时候，他可能会经过正在吃草的同伴旁。当路过已经有奶牛的牧场时，奶牛i会放

慢自己的速度，防止打扰他的朋友。 考虑如下的牧场结构（括号内的数字代表了牧场的所有者）。

输入

* 第1行 : 一个正整数N * 第2…N行: 第i+1行包括一对正整数A_i,B_i * 第N+1..N+N行: 第 N+i行 包括一个正整数: P_i

输出

* 第一行到第N行：第i行表示第i只奶牛需要被放慢的次数

样例输入

5
1 4
5 4
1 3
2 4
4
2
1
5
3

样例输出

0
1
0
2
1

题目大意就是求每个点到根节点的链上有几个点的点权(就是奶牛编号)比这个点小。看其他人都是什么拿树状数组、树链剖分、线段树过的。最近写平衡树比较爽的我就拿treap写了一下。首先求一条链(也就是一个数列)上比这个数小的数有多少个，直接求一下当前数在数列中的排名就好了，这个直接裸上treap。但因为只考虑这条链上的点，所以要在每次回溯到一个点时把这个点从treap中删除。

最后附上代码。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int x,y;
int tot;
int root;
int a[100010];
int s[100010];
int r[300010];
int v[300010];
int g[100010];
int to[200010];
int ls[300010];
int rs[300010];
int head[100010];
int next[200010];
int size[300010];
void add(int x,int y)
{
    tot++;
    next[tot]=head[x];
    head[x]=tot;
    to[tot]=y;
}
void up(int x)
{
    size[x]=size[rs[x]]+size[ls[x]]+1;
}
void rturn(int &x)
{
    int t;
    t=ls[x];
    ls[x]=rs[t];
    rs[t]=x;
    size[t]=size[x];
    up(x);
    x=t;
}
void lturn(int &x)
{
    int t;
    t=rs[x];
    rs[x]=ls[t];
    ls[t]=x;
    size[t]=size[x];
    up(x);
    x=t;
}
void insert_sum(int x,int &i)
{
    if(!i)
    {
        i=++tot;
        size[i]=1;
        v[i]=x;
        r[i]=rand();
        return ;
    }
    size[i]++;
    if(x>v[i])
    {
        insert_sum(x,rs[i]);
        if(r[rs[i]]<r[i])
        {
            lturn(i);
        }
    }
    else
    {
        insert_sum(x,ls[i]);
        if(r[ls[i]]<r[i])
        {
            rturn(i);
        }
    }
    return ;
}
void delete_sum(int x,int &i)
{
    if(i==0)
    {
        return ;
    }
    if(v[i]==x)
    {
        if((ls[i]*rs[i])==0)
        {
            i=ls[i]+rs[i];
        }
        else if(r[ls[i]]<r[rs[i]])
        {
            rturn(i);
            delete_sum(x,i);
        }
        else
        {
            lturn(i);
            delete_sum(x,i);
        }
        return ;
    }
    size[i]--;
    if(v[i]<x)
    {
        delete_sum(x,rs[i]);
    }
    else
    {
        delete_sum(x,ls[i]);
    }
    return ;
}
int ask_num(int x,int i)
{
    if(i==0)
    {
        return 0;
    }
    if(v[i]==x)
    {
        return size[ls[i]]+1;
    }
    if(v[i]<x)
    {
        return ask_num(x,rs[i])+size[ls[i]]+1;
    }
    return ask_num(x,ls[i]);
}
void dfs(int x,int fa)
{
    for(int i=head[x];i;i=next[i])
    {
        if(to[i]!=fa)
        {
            g[s[to[i]]]=ask_num(s[to[i]],root);
            insert_sum(s[to[i]],root);
            dfs(to[i],x);
            delete_sum(s[to[i]],root);
        }
    }
}
int main()
{
    srand(12378);
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s[a[i]]=i;
    }
    insert_sum(s[1],root);
    g[s[1]]=0;
    dfs(1,1);
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",g[i]);
    }
}