Problem Description
You are given a tree, it’s root is p, and the node is numbered from 1 to n. Now define f(i) as the number of nodes whose number is less than i in all the succeeding nodes of node i. Now we need to calculate f(i) for any possible i.
Input
Multiple cases (no more than 10), for each case:The first line contains two integers n (0<n<=10^5) and p, representing this tree has n nodes, its root is p.Following n-1 lines, each line has two integers, representing an edge in this tree.The input terminates with two zeros.
Output
For each test case, output n integer in one line representing f(1), f(2) … f(n), separated by a space.
Sample Input
15 77 107 17 97 37 410 1414 214 139 119 66 56 83 153 120 0
Sample Output
0 0 0 0 0 1 6 0 3 1 0 0 0 2 0
题意：求以x为根节点的子树权值和。
题解：求得dfs序之后，就是简单的求和问题，BIT/线段树均可。
因为题目是求比当前x小的，，所以我们要从大的开始更新。不想手动模拟请加栈
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<string>#include<iostream>#include<queue>#include<cmath>#include<map>#include<stack>#include<bitset>using namespace std;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )#define CLEAR( a , x ) memset ( a , x , sizeof a )typedef long long LL;typedef pair<int,int>pil;const int INF = 0x3f3f3f3f;const int maxn=1e5+100;int L[maxn],R[maxn];int c[maxn*2+10];vector<int>v[maxn];int ans[maxn];int n,rt,dfn;void dfs(int u,int pre){L[u]=++dfn;for(int i=0;i<v[u].size();i++){int to=v[u][i];if(to==pre) continue;dfs(to,u);}R[u]=++dfn;}int lowbit(int x){return x&(-x);}void update(int x,int val){while(x<=dfn){c[x]+=val;x+=lowbit(x);}}int query(int x){int sum=0;while(x>0){sum+=c[x];x-=lowbit(x);}return sum;}int main(){int x,y;while(~scanf("%d%d",&n,&rt),n+rt){CLEAR(L,0);REP(i,n+1)v[i].clear();for(int i=0;i<n-1;i++){scanf("%d%d",&x,&y);v[x].push_back(y);v[y].push_back(x);}dfn=0;dfs(rt,-1);CLEAR(c,0);for(int i=1;i<=dfn;i++)update(i,1);for(int i=n;i>=1;i–){ans[i]=(query(R[i]-1)-query(L[i]))/2;update(R[i],-1);update(L[i],-1);}REPF(i,1,n)printf(i==n?"%d\n":"%d ",ans[i]);}return 0;}
我们一直在旅行，一直在等待某个人可以成为我们旅途的伴侣，
