Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- //#include <bits/stdc++.h>
- using namespace std;
- const int maxn = 2e5 + 2;
- const int logn = 19;
- int n, q;
- vector<int> graph[maxn];
- int in_dfs[maxn], out_dfs[maxn];
- int pref_sum[maxn];
- int up_node[maxn][logn];
- int timer = 0;
- void dfs(int node, int parent) {
- timer++;
- in_dfs[node] = timer;
- up_node[node][0] = parent;
- for(int i = 1; i < logn; i++) {
- up_node[node][i] = up_node[up_node[node][i - 1]][i - 1];
- }
- for(int neighbour : graph[node]) {
- if(neighbour != parent) {
- dfs(neighbour, node);
- }
- }
- timer++;
- out_dfs[node] = timer;
- }
- bool is_ancestor(int A, int B) {
- if(in_dfs[A] <= in_dfs[B] and out_dfs[A] >= out_dfs[B]) {
- return true;
- }
- return false;
- }
- int LCA(int A, int B) {
- if(is_ancestor(A, B)) {
- return A;
- }
- if(is_ancestor(B, A)) {
- return B;
- }
- for(int i = logn - 1; i >= 0; i--) {
- if(!is_ancestor(up_node[A][i], B)) {
- A = up_node[A][i];
- }
- }
- // cout << A << endl;
- if(A == 0) {
- return 1;
- }
- return up_node[A][0];
- }
- void pref_dfs(int node) {
- for(int neighbour : graph[node]) {
- if(neighbour != up_node[neighbour][0]) {
- pref_dfs(neighbour);
- pref_sum[node] += pref_sum[neighbour];
- }
- }
- }
- int main(){
- ios_base::sync_with_stdio(false);
- cin >> n >> q;
- for(int i = 1; i < n; i++) {
- int a, b;
- cin >> a >> b;
- graph[a].push_back(b);
- graph[b].push_back(a);
- }
- dfs(1, -1);
- for(int i = 0; i < q; i++) {
- int a, b;
- cin >> a >> b;
- pref_sum[a]++;
- pref_sum[b]++;
- int lca = LCA(a, b);
- // cout << a << " "<< b << " " << lca<< endl;
- pref_sum[lca]--;
- if(lca != 1) {
- pref_sum[up_node[lca][0]]--;
- }
- }
- // for(int i = 1; i <= n; i++) {
- // cout << pref_sum[i] << " ";
- // }
- // cout << endl;
- pref_dfs(1);
- for(int i = 1; i <= n; i++) {
- cout << pref_sum[i] << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement