arbori_nr

#include <fstream>
#include <vector>
using namespace std;
using VI=vector<int>;
using VVI=vector<VI>;
int n,r;
VVI G;
VI aib,aiblant;
VI rez,lant;

void update(int pos,int val)
{
    for(int i=pos;i<=n;i+=i&-i)
        aib[i]+=val;
}

int query(int pos)
{
    int sum=0;
    for(int i=pos;i>0;i-=i&-i)
        sum+=aib[i];
    return sum;
}

void updatelant(int pos,int val)
{
    for(int i=pos;i<=n;i+=i&-i)
        aiblant[i]+=val;
}

int querylant(int pos)
{
    int sum=0;
    for(int i=pos;i>0;i-=i&-i)
        sum+=aiblant[i];
    return sum;
}

void dfs1(int node,int dad)
{
    update(node,1);
    updatelant(node,1);
    rez[node]+=query(node-1);
    for(int i=0;i<(int) G[node].size();++i)
        if(G[node][i]!=dad)
            dfs1(G[node][i],node);
    updatelant(node,-1);
    lant[node]=querylant(node);
}

void dfs2(int node,int dad)
{
    update(node,1);
    rez[node]+=query(node-1);
    for(int i=G[node].size()-1;i>=0;--i)
        if(G[node][i]!=dad)
            dfs2(G[node][i],node);
}

int main()
{
    ifstream f("arbori_nr.in");
    f>>n>>r;
    G=VVI(n+1);
    rez=VI(n+1);
    lant=VI(n+1);
    aib=VI(4*n+1);
    aiblant=VI(4*n+1);
    for(int i=1,x,y;i<n;++i)
        f>>x>>y,G[x].push_back(y),G[y].push_back(x);
    f.close();
    dfs1(r,0);
    for(int i=0;i<4*n;++i)
        aib[i]=0;
    dfs2(r,0);
    ofstream g("arbori_nr.out");
    for(int i=1;i<=n;++i)
        g<<i-rez[i]+lant[i]-1<<' ';
    g.close();
    return 0;
}