CSU 1414: Query on a Tree

CSU 1414: Query on a Tree2015-02-17预处理每个结点的子结点的个数sons , 则对x的询问可由sons[x]- sigma（ sons[v] ）（v是到x距离为d的点）得到

怎么快速的找到这些v呢？注意到距离x为d的点肯定在树的同一层....

可以对树进行dfs时记录每个结点时间戳的同时把每一层的结点保存下来,然后对每一层维护一个前缀和如果v是x下面子结点那么v的时间戳肯定在x的范围内,这样就可以二分確定出前缀和的范围了.....

1414: Query on a Tree
Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 78 Solved: 23
[Submit][Status][Web Board]
Description
You are given a rooted tree with N nodes indexed by 1, 2, ..., N, and the root is indexed by 1. We will ask you to perform some queries of the following form:
x d : Ask for how many nodes there are in the subtree rooted at x, such that the distance between it and x is less than d.
Assume the length of each edge is 1.
Input
The first line contains an integer T （T > 0）, giving the number of test cases.
For each test case, the first line contains an integer N （2 ≤ N ≤ 105）. The next line contains N - 1 integers f2, f3, ..., fN （1 ≤ f2, f3, ..., fn ≤ N）, where fi （2 ≤ i ≤ N） denotes the father of i is fi. Then follows a line with an integer M （1 ≤ M ≤ 105） giving the number of queries. Then follow M lines with two integers x, d （1 ≤ x, d ≤ N）, giving the M queries.
Output
For each query, output how many nodes there are in the subtree rooted at x, such that the distance between it and x is less than d.
Sample Input

1
9
1 2 2 4 4 2 1 8
6
1 1
1 2
1 3
2 3
2 4
3 2

Sample Output

1
3
7
6
6
1

HINT

Source

中南大学第八届大学生程序设计竞赛
[Submit][Status][WebBoard]

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>using namespace std;const int maxn=110000;struct Edge{int to,next;}edge[maxn];int Adj[maxn],Size;vector<int> eg[maxn];vector<int> pre_sum[maxn];int dfn[maxn][2],sons[maxn],max_deep[maxn],Deep[maxn],id[maxn],ti,maxdeep,n;void init（int n）{Size=0;memset（Adj,-1,sizeof（Adj））;memset（dfn,0,sizeof（dfn））;memset（sons,0,sizeof（sons））;memset（Deep,0,sizeof（Deep））;memset（id,0,sizeof（id））;memset（max_deep,0,sizeof（max_deep））;ti=0;maxdeep=0;for（int i=0;i<=n+20;i++）{pre_sum[i].clear（）,pre_sum[i].push_back（0）;eg[i].clear（）,eg[i].push_back（0）;}}void Add_Edge（int u,int v）{edge[Size].to=v;edge[Size].next=Adj[u];Adj[u]=Size++;}void DFS（int u,int deep）{dfn[u][0]=++ti;maxdeep=max（maxdeep,deep）;eg[deep].push_back（u）;int maxd=0;for（int i=Adj[u];~i;i=edge[i].next）{int v=edge[i].to;DFS（v,deep+1）;maxd=max（maxd,max_deep[v]）;}max_deep[u]=maxd+1;Deep[u]=deep;dfn[u][1]=ti;sons[u]=dfn[u][1]-dfn[u][0]+1;}void prefix_sum（）{for（int i=1;i<=maxdeep;i++）{for（int j=1,sz=eg[i].size（）;j<sz;j++）{id[eg[i][j]]=j;pre_sum[i].push_back（ pre_sum[i][j-1]+sons[eg[i][j]] ）;}}}void Debug（）{for（int i=1;i<=n;i++）{cout<<i<<" st: "<<dfn[i][0]<<" et: "<<dfn[i][1]<<" sons: "<<sons[i]<<endl;}cout<<"maxdeep: "<<maxdeep<<endl;for（int i=1;i<=maxdeep;i++）{cout<<i<<": "<<endl;for（int j=0,sz=eg[i].size（）;j<sz;j++）{cout<<eg[i][j]<<",";}cout<<endl;}cout<<"id: 
";for（int i=1;i<=maxdeep;i++）{cout<<i<<": "<<endl;for（int j=0,sz=eg[i].size（）;j<sz;j++）{cout<<id[eg[i][j]]<<",";}cout<<endl;}cout<<"prefix_sum: 
";for（int i=1;i<=maxdeep;i++）{cout<<i<<": "<<endl;for（int j=0,sz=eg[i].size（）;j<sz;j++）{cout<<pre_sum[i][j]<<",";}cout<<endl;}cout<<"max_deep: ";for（int i=1;i<=n;i++）{cout<<i<<" : "<<max_deep[i]<<endl;}}void solve（int x,int d）{int nowd=Deep[x];if（d>=max_deep[x]）{printf（"%d
",sons[x]）;return ;}int qd=nowd+d;///二分左右区间int L=0,R=0,sz=eg[qd].size（）;int low,mid,high;///....get left poslow=0,high=sz-1;while（low<=high）{mid=（low+high）/2;int ps=eg[qd][mid];if（dfn[ps][0]>=dfn[x][0]）{L=eg[qd][mid-1]; high=mid-1;}else low=mid+1;}///...get right poslow=0,high=sz-1;while（low<=high）{mid=（low+high）/2;int ps=eg[qd][mid];if（dfn[ps][1]<=dfn[x][1]）{R=ps; low=mid+1;}else high=mid-1;}printf（"%d
",sons[x]-pre_sum[qd][id[R]]+pre_sum[qd][id[L]]）;}int main（）{int T_T;scanf（"%d",&T_T）;while（T_T--）{scanf（"%d",&n）;init（n+1）;for（int i=2;i<=n;i++）{int fa;scanf（"%d",&fa）;Add_Edge（fa,i）;}DFS（1,1）;prefix_sum（）; // Debug（）;int q;scanf（"%d",&q）;while（q--）{int x,d;scanf（"%d%d",&x,&d）;solve（x,d）;}}return 0;}

From：csdn博客码代码的猿猿