为什么网站显示乱码,昆山做网站的个人,佛山优秀网站建设,免费法律咨询武当派一共有 nnn 人#xff0c;门派内 nnn 人按照武功高低进行排名#xff0c;武功最高的人排名第 111#xff0c;次高的人排名第 222#xff0c;... 武功最低的人排名第 nnn。现在我们用武功的排名来给每个人标号#xff0c;除了祖师爷#xff0c;每个人都有一个师父门派内 nnn 人按照武功高低进行排名武功最高的人排名第 111次高的人排名第 222... 武功最低的人排名第 nnn。现在我们用武功的排名来给每个人标号除了祖师爷每个人都有一个师父每个人可能有多个徒弟。
我们知道武当派人才辈出连祖师爷的武功都只能排行到 ppp。也就是说徒弟的武功是可能超过师父的所谓的青出于蓝胜于蓝。
请你帮忙计算每个人的所有子弟包括徒弟的徒弟徒弟的徒弟的徒弟....中有多少人的武功超过了他自己。
输入格式
输入第一行两个整数 n,p(1≤n≤100000,1≤p≤n)n, p(1 \le n \le 100000, 1 \le p \le n)n,p(1≤n≤100000,1≤p≤n)。
接下来 n−1n-1n−1 行每行输入两个整数 u,v(1≤u,v≤n)u, v(1 \le u, v \le n)u,v(1≤u,v≤n)表示 uuu 和 vvv 之间存在师徒关系。
输出格式
输出一行 nnn 个整数第 iii 个整数表示武功排行为 iii 的人的子弟有多少人超过了他。行末不要输出多余的空格。样例输入 10 5
5 3
5 8
3 4
3 1
2 1
6 7
8 7
9 8
8 10 样例输出 0 0 2 0 4 0 1 2 0 0题意就是给我们一颗树 让我们求 每个点的所以所有孩子节点有多少比自己小的节点的数量可以dfs下把所有节点的父节点找到 然后每个点不断地向上找父节点 一直找到根 这样的复杂度接近n的平方级 肯定超时为了不超时我们可以把整颗树的DFS序搞出来 然后任意一个节点的先序和后序顺序 中间的差就是这个点的孩子节点的个数 但是我们要找的是孩子节点中比他小的节点 那么我们就可以dfs序和树状数组配合起来 dfs序把树形问题转化成了区间上的问题我们知道这个点的先序和后序位次 那么如果有比他小的节点在这个节点的先序和后序之间遍历到了那么一定是符合要求的点 所以我们可以从小大到处理点 对于每个点查询先序后序位置中树状数组存储的差 然后再把当前节点的先序插入进去 这样的好处就是先遍历标号小的节点 先把小的节点的先序插到树状数组树状数组维护的就是当前节点先序插入时的次序 因为我们是通过前序后序间符合条件的点数来求解的 import java.util.ArrayList;
import java.util.Scanner;
import java.util.Vector;public class Main {final static int maxn 100010; public static int [] tre new int[maxn];public static ArrayListInteger[] gra new ArrayList[maxn];//存图public static boolean[] bok new boolean[maxn];public static boolean[] vis new boolean[maxn];public static int[] l new int[maxn];//记录先序public static int[] r new int[maxn];//记录第二次回溯回来时的顺序public static int time 0 ;static void DFS(int now) {l[now] time;for(int i0;igra[now].size();i) {int t gra[now].get(i);if(!vis[t]) {vis[t]true;DFS(t);vis[t]false;}}r[now] time;}static void add(int x) {while(xmaxn) {tre[x]1;xx(-x);}}static int sum(int x) {int S0;while(x!0) {Stre[x];x-x(-x);}return S;}public static void main(String[] args) {int n,p;Scanner sc new Scanner(System.in);n sc.nextInt();p sc.nextInt();for(int i1;in;i) {int s,e;s sc.nextInt();e sc.nextInt();if(bok[s]false) {bok[s] true;gra[s] new ArrayListInteger();gra[s].add(e);}else gra[s].add(e);if(bok[e]false) {bok[e] true;gra[e] new ArrayListInteger();gra[e].add(s);}else gra[e].add(s);}vis[p]true;DFS(p);for(int i1;in;i) {System.out.print(sum(r[i])-sum(l[i]));add(l[i]);if(in)System.out.println();else System.out.print( );}}
}
