CSES - Shared codeLink to this code:
https://cses.fi/paste/76b082b9448a13798977a8/#include <bits/stdc++.h>
using namespace std;
#define ar array
#define ascii_lowercase "abcdefghijklmnopqrstuvwxyz"
#define ascii_uppercase "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define int long long
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
#define yes "yes"
#define no "no"
#define mod 1000000007
#define endl '\n'
#define add insert
using vec2D = vector<vector<int>>;
using vec1D = vector<int>;
#define fo(i, a, b) for (int i = a; i < b; ++i)
#define ro(i, a, b) for (int i = a; i >b; --i)
// #define fo(i, a, b, ...) for (int i = a; i < b; i+=(__VA_ARGS__ == NULL ? 1 : __VA_ARGS__))
// #define ro(i, a, b, ...) for (int i = a; i > b; i-=(__VA_ARGS__ == NULL ? 1 : __VA_ARGS__))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define len(x) (int)(x.size())
#define fi first
#define se second
#define append push_back
// #define tuple make_pair
#define gh(x) {cout << (x) << '\n';}
// #define Outd(x) {printf("%.10f",x);cout<<endl;}
#define print_vec(vec) { for (size_t iii = 0; iii < vec.size(); iii++) { if (iii == vec.size() - 1) std::cout << vec[iii] << '\n'; else std::cout << vec[iii] << ' '; } }
template<class... T> void in(T&... x) {(cin >> ... >> x);}
#define integer(...) int __VA_ARGS__; in(__VA_ARGS__);cin.ignore();
#ifndef ONLINE_JUDGE
#define de(var) {cerr << #var << ": "; debug_view(var);}
template<typename T> inline void debug_view(T e){cerr << e << endl;}
template<typename T> inline void debug_view(pair<T,T> p){cerr << p.first << ' ' << p.second << endl;}
template<typename T> inline void debug_view(queue<T> q){while(!q.empty()) {cerr << q.front() << " "; q.pop();}cerr << endl;}
template<typename T> inline void debug_view(deque<T> q){for(auto i:q) {cerr << i << " ";}cerr << endl;}
template<typename T> inline void debug_view(set<T> s){for(auto x:s){cerr << x << ' ';}cerr << endl;}
template<typename T> inline void debug_view(multiset<T> s){for(auto x:s){cerr << x << ' ';}cerr << endl;}
template<typename T> inline void debug_view(vector<pair<T,T>> &v){for(auto [a,b]: v){cerr<<"{"<<a<<" "<<b<<"} ";} cerr << endl;}
template<typename T> inline void debug_view(vector<T> &v){for(auto e: v){cerr << e << " ";} cerr << endl;}
template<typename T> inline void debug_view(vector<vector<pair<T,T>>> &vv){cerr << "----" << endl;for(auto &v: vv){debug_view(v);} cerr << "--------" << endl;}
template<typename T> inline void debug_view(vector<vector<T>> &vv){cerr << "----" << endl;for(auto &v: vv){debug_view(v);} cerr << "--------" << endl;}
// template<typename T> inline void debug_view(vector<ar> &vv){cerr << "----" << endl;for(auto &v: vv){debug_view(v);} cerr << "--------" << endl;}
template<typename T1,typename T2> inline void debug_view(map<T1,T2> &mp){cerr << "----" << endl;for(auto [k,v]: mp){cerr << k << ' ' << v << endl;} cerr << "--------" << endl;}
template<typename T1,typename T2> inline void debug_view(unordered_map<T1,T2> &mp){cerr << "----" << endl;for(auto [k,v]: mp){cerr << k << ' ' << v << endl;} cerr << "--------" << endl;}
template<typename T1,typename T2> inline void debug_view(map<T1,vector<T2>> &mp){cerr<<"----"<<endl;for(auto [k,v]: mp){cerr<<k<<": ";debug_view(v);} cerr << "--------" << endl;}
template<typename T1,typename T2,typename T3> inline void debug_view(map<pair<T1,T2>,T3> &mp){cerr << "----" << endl;for(auto [p,v]: mp){cerr<<'{'<<p.first<<' '<<p.second<<'}'<<": "<<v<<endl;} cerr<<"--------"<<endl;}
#define deb(var) {cerr << #var << ": "; debugb_view(var);}
template<typename T> inline void debugb_view(T e){bitset<20> b(e); cerr<<b<<endl;}
template<typename T> inline void debugb_view(vector<T> &v){cerr<<"----"<<endl;for(auto e: v){debugb_view(e);}}
#else
#define de(var) {}
#endif
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
unordered_map<T, int> Counter(const vector<T>& a) {
unordered_map<T, int> counts;
for (const T& x : a) {
counts[x]++;
}
return counts;
}
vector<int> lst() {
string input;
getline(cin, input);
stringstream ss(input);
vector<int> result;
int num;
while (ss >> num) {
result.push_back(num);
}
return result;
}
// int integer() {
// int num;
// cin >> num;
// cin.ignore();
// return num;
// }
string st() {
string s;
getline(cin, s);
if (!s.empty() && s[s.length()-1] == '\n') {
s.erase(s.length()-1);
}
return s;
}
vector<vector<int>> matrixNum(int m) {
vector<vector<int>> result;
for (int i = 0; i < m; ++i) {
result.push_back(lst());
}
return result;
}
vector<string> matrixStr(int m) {
vector<string> matrix;
for (int i = 0; i < m; i++) {
matrix.push_back(st());
}
return matrix;
}
bool h(int i, int j, string& s, vector<vector<char>>& sp) {
int r = sp.size();
int c = sp[0].size();
for (char d : s) {
if (d == 'U') {
i--;
} else if (d == 'R') {
j++;
} else if (d == 'D') {
i++;
} else if (d == 'L') {
j--;
}
if (i >= 0 && i < r && j >= 0 && j < c) {
if (sp[i][j] == '#') {
return false;
}
} else {
return false;
}
}
return sp[i][j] == '.';
}
template<typename T>
typename T::value_type sum(const T& container) {
return std::accumulate(container.begin(), container.end(), typename T::value_type());
}
ll max(ll a, ll b) {
if (a > b)
return a;
else
return b;
}
ll min(ll a, ll b) {
if (a < b)
return a;
else
return b;
}
int gcd(int a, int b) {
if (a == 0)
return b;
return gcd(b % a, a);
}
int findGCD(vector<int>& arr, int n) {
int result = arr[0];
for (int i = 1; i < n; i++) {
result = gcd(arr[i], result);
if (result == 1) {
return 1;
}
}
return result;
}
// int power(int x, unsigned int y, unsigned int M) {
// if (y == 0)
// return 1;
// int p = power(x, y / 2, M) % M;
// p = (p * p) % M;
// return (y % 2 == 0) ? p : (x * p) % M;
// }
int power(int base, unsigned int exponent, unsigned int modulus) { //int power(int base, int exponent, int modulus) {
int result = 1;
base = base % modulus;
while (exponent > 0) {
if (exponent % 2 == 1) {
result = (result * base) % modulus;
}
exponent = exponent >> 1;
base = (base * base) % modulus;
}
return result;
}
int modInverse(int A, int M) // returns modular inverse (works when M is prime)
{
int g = gcd(A, M);
if (g != 1) { // inverse doesnt exist
return 0;
}
else {
// If a and m are relatively prime, then modulo
// inverse is a^(m-2) mod m
return power(A, M - 2, M);
}
}
bool isPrime(int n) // O(rt(n))
{
// Corner cases
if (n <= 1)
return false;
if (n<4)
return true;
if (n%2==0 || n%3==0 || n%5==0)
return false;
// suppose n=7 that is prime and its pair are (1,7)
// so if a no. is prime then it can be check by numbers smaller than square root
// of the n
for (int i = 2; i * i <= n; i++) {
if (n % i == 0)
return false;
}
return true;
}
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
vector<int> myprimes;
unordered_set<int,custom_hash> myprimess;
void SieveOfEratosthenes(int n) {
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
vector<bool> prime(n + 1, true);
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed, then it is a prime
if (prime[p] == true) {
// Update all multiples of p greater than or
// equal to the square of it numbers which are
// multiple of p and are less than p^2 are
// already been marked.
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
// Print all prime numbers
for (int p = 2; p <= n; p++)
if (prime[p]) {
myprimes.push_back(p);
myprimess.insert(p);
}
}
void primeFactors(int n) {
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) myprimes.push_back(i);
while (n % i == 0) n /= i;
}
if (n > 1) myprimes.push_back(n);
}
class DSU {
private:
vector<int> p,rank,setSize;
int numSets;
public:
DSU(int n) {
n++;
p.assign(n,0);
for (int i = 0; i < n; i++) {
p[i] = i;
}
rank.assign(n,0); // height of all trees are 0.
setSize.assign(n,1); // size of individual sets are 1
numSets = n-1;
}
int find(int x) {
if (p[x]==x) return x;
return p[x] = find(p[x]); // path compression
}
bool same(int x, int y) {return find(x)==find(y);}
bool unionn(int i, int j) {
// if (same(i,j)) return false;
int x = find(i);
int y = find(j);
if (x==y) return true;
if (rank[x]>rank[y]) swap(x,y);
p[x] = y;
if (rank[x]==rank[y]) rank[y]++;
setSize[y] += setSize[x];
numSets--;
return false;
}
int size(int x) {
return setSize[x];
}
int numDisjointSets() {
return numSets;
}
};
// bool cmp(const vector<int>& a,const vector<int>& b) {
// return a[1]<b[1];
// }
// bool cmp(pair<int,int> &a, pair<int,int> &b)
// {
// return a.second < b.second;
// }
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
vector<vector<int>> d4 = {{1,0},{0,1},{-1,0},{0,-1}};
vector<vector<int>> d8 = {{0,1},{1,0},{0,-1},{-1,0},{1,-1},{-1,1},{1,1},{-1,-1}};
unordered_map<char,vector<int>> dir={
{'U', {-1, 0}},
{'R', {0, 1}},
{'D', {1, 0}},
{'L', {0, -1}}
};
vector<int> djisktra(int src, const vector<vector<pair<int, int>>>& d, int n) {
vector<int> p(n + 1, inf);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> a;
a.push({0, src});
p[src] = 0;
while (!a.empty()) {
auto [di, node] = a.top();
a.pop();
if (p[node]<di) continue;
for (auto [j, weight] : d[node]) {
if (di+ weight < p[j]) {
p[j] = di + weight;
a.push({p[j], j});
}
}
}
return p;
}
// int vis[1001][1001];
// vector<int> parent[1001][1001];
// char dd[1001][1001];
// int dp[100005][2],vis[100005];
// 0x3f
// const int mxn = 2e5+5;
// int n,m, coins[mxn],par[mxn],dp[mxn],maxi;
// vector<int> adj[mxn],adj2[mxn],adj3[mxn];
// vector<int> stk;
// bool vis[mxn];
template<typename T>
void dea(const T &a, int l, int r) {
for (int i = l; i < r; ++i) {
cerr << a[i] << " ";
}
cerr << endl;
}
void precompute(){
}
const int mxN = 2*(1e5)+4;
// const int maxm = 5500;
int n,q, dp[18][mxN], depth[mxN],res[mxN];
vector<int> adj[mxN];
// int a[mxN];
void dfs(int u, int par){
for (auto v:adj[u]){
if (v==par)continue;
dp[0][v] = u;
depth[v] = max(depth[v],1+depth[u]);
dfs(v,u);
}
}
void dfs2(int u, int par){
for (auto v:adj[u]){
if (v==par)continue;
dfs2(v,u);
res[u] += res[v];
}
}
void solve()
{
cin>>n>>q;
memset(dp,-1,sizeof(dp));
fo(i,0,n-1){
integer(u,v);
u--;v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(0,-1);
fo(i,1,18){
fo(j,0,n){
if (dp[i-1][j]==-1){
dp[i][j] = -1;continue;
}
dp[i][j] = dp[i-1][dp[i-1][j]];
}
}
// int res[n];
while (q--){
integer(a,b);
a--;b--;
if (depth[a]>depth[b]){
swap(a,b);
}
res[a]++;
res[b]++;
int dif = depth[b]-depth[a];
int b1 = b;
int a1 = a;
// int x = b;
fo(i,0,18)
{
if (dif&(1<<i)){
b1 = dp[i][b1];
if (b1==-1)
break;
}
}
int lca;
if (a1==b1){
lca = a1;
}else{
fo(i,0,18){
if (dp[i][a1]==dp[i][b1]){
break;
}
a1 = dp[i][a1];
b1 = dp[i][b1];
}
lca = dp[0][a1];
}
res[lca]-=1;
if (dp[0][lca]!=-1){
lca = dp[0][lca];
res[lca]-=1;
}
// dea(res,0,n);
}
dfs2(0,-1);
fo(i,0,n){
cout<<res[i]<<" ";
}
// gh(res);
}
int32_t main() {
auto begin = std::chrono::high_resolution_clock::now();
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
// integer(t);
precompute();
while (t--)
{
solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
} 