Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int INF = (1<<30);
- const ll inf = (1LL << 55LL);
- const int maxn = 300004;
- vector<int> graph[maxn];
- int arr[maxn];
- int parent[maxn];
- bool visited[maxn];
- //1000000000
- int n, S;
- int tmpArr[maxn];
- int ret;
- void dfs(int node){
- if(node == 0){
- return;
- }
- int sosed;
- for(int i =0 ; i <(int)graph[node].size(); i ++){
- sosed = graph[node][i];
- if(sosed != parent[node])continue;
- if(tmpArr[node] > tmpArr[sosed]){
- ret ++;
- tmpArr[sosed] = tmpArr[node] ;
- dfs(sosed);
- }
- }
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin >> n >> arr[0];
- int a, b;
- for(int i = 1; i <= n; i ++){
- cin >> arr[i] >> b;
- a = i;
- parent[i] = b;
- graph[a].push_back(b);
- graph[b].push_back(a);
- }
- for(int j = 0; j <= n; j ++){
- tmpArr[j] = arr[j];
- }
- for(int i = 1; i <= n; i ++){
- ret = 0;
- S = i;
- dfs(i);
- cout << ret << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement