程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 3887 Counting Offspring(DFS序求子樹權值和)

HDU 3887 Counting Offspring(DFS序求子樹權值和)

編輯:關於C++
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 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 7
7 10
7 1
7 9
7 3
7 4
10 14
14 2
14 13
9 11
9 6
6 5
6 8
3 15
3 12
0 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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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 pairpil;
const int INF = 0x3f3f3f3f;
const int maxn=1e5+100;
int L[maxn],R[maxn];
int c[maxn*2+10];
vectorv[maxn];
int ans[maxn];
int n,rt,dfn;
void dfs(int u,int pre)
{
    L[u]=++dfn;
    for(int i=0;i0)
    {
        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=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;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved