查询树上某个节点的子节点的标号小于其标号的数目. 一个trick是建立线段树之后,从标号小的向标号大的来做更新.
1: #include <cstdio>
2: #include <cstring>
3: #include <cctype>
4: #include <algorithm>
5: #include <vector>
6: #include <iostream>
7: using namespace std;
8: #pragma comment(linker, "/STACK:1024000000,1024000000")
9: #define LL(a) a<<1
10: #define RR(a) a<<1|1
11:
12: const int MaxL = 200030;
13:
14: int pre[MaxL]; // first travel
15: int nxt[MaxL]; // nxt travel
16: int f[MaxL];
17: bool vis[MaxL];
18: int N;
19: vector<vector<int> > E(MaxL);
20:
21: struct Seg_tree
22: {
23: int left, right;
24: int sum;
25: } tt[MaxL<<2];
26:
27:
28: void PushUp(int idx)
29: {
30: tt[idx].sum = tt[LL(idx)].sum + tt[RR(idx)].sum;
31: }
32:
33: void build(int l,int r,int idx)
34: {
35: tt[idx].left = l, tt[idx].right = r;
36: tt[idx].sum = 0;
37: if (l == r) return ;
38: int m = (l + r) >> 1;
39: build(l,m, LL(idx));
40: build(m+1, r, RR(idx));
41: }
42:
43: void update(int p, int idx = 1)
44: {
45: if(p == tt[idx].left && p == tt[idx].right)
46: {
47: tt[idx].sum =1;
48: return ;
49: }
50: int mid = (tt[idx].left + tt[idx].right)>>1;
51: if(p <= mid) update(p, LL(idx));
52: else update(p, RR(idx));
53: PushUp(idx);
54: }
55:
56: int query(int l, int r, int idx = 1)
57: {
58: if(l == tt[idx].left && r ==tt[idx].right)
59: return tt[idx].sum;
60: int mid = (tt[idx].left + tt[idx].right)>>1;
61: if(r <= mid) return query(l,r, LL(idx));
62: else if(l> mid) return query(l,r, RR(idx));
63: else
64: return query(l, mid, LL(idx))+ query(mid+1, r, RR(idx));
65: }
66:
67: int mark = 1;
68: void dfs( int a)
69: {
70: vis[a] = 1;
71: pre[a] = mark++;
72: for(int i=0; i<E[a].size(); i++)
73: {
74: if(!vis[E[a][i]])
75: dfs(E[a][i]);
76: }
77: nxt[a] = mark++;
78: }
79:
80: int main()
81: {
82: // freopen("1.txt","r",stdin);
83: int p;
84: while( scanf("%d%d", &N, &p) && N!=0 && p!=0)
85: {
86: memset(pre, 0, sizeof(pre));
87: memset(nxt, 0 ,sizeof(nxt));
88: memset(vis, 0 ,sizeof(vis));
89: for(int i=1; i<=N; i++) E[i].clear();
90:
91: for(int i=1; i<N; i++)
92: {
93: int a,b;
94: scanf("%d%d", &a,&b);
95: E[a].push_back(b);
96: E[b].push_back(a);
97: }
98: mark = 1;
99: dfs(p);
100: build(1, 2*N, 1);
101: for(int i=1; i<=N; i++)
102: {
103: f[i] =query(pre[i], nxt[i],1);
104: update(pre[i],1);
105: }
106: for(int i=1; i<N; i++)
107: printf("%d ",f[i]);
108: printf("%d\n",f[N]);
109: }
110: return 0;
111: }
.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }