Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Nguyen Huu Hoang Minh
- #include <bits/stdc++.h>
- #define sz(x) int(x.size())
- #define all(x) x.begin(),x.end()
- #define reset(x) memset(x, 0,sizeof(x))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define N 200005
- #define remain(x) if (x > MOD) x -= MOD
- #define ii pair<int, int>
- #define iiii pair< ii , ii >
- #define viiii vector< iiii >
- #define vi vector<int>
- #define vii vector< ii >
- #define bit(x, i) (((x) >> (i)) & 1)
- #define Task "test"
- using namespace std;
- typedef long double ld;
- int n, m;
- vector<int> g[N];
- void readfile()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- if (fopen(Task".inp","r"))
- {
- freopen(Task".inp","r",stdin);
- //freopen(Task".out","w",stdout);
- }
- cin >> n;
- for(int i=1; i<n; i++){
- int u, v; cin >> u >> v;
- g[u].pb(v);
- g[v].pb(u);
- }
- }
- int Start[N], Depth[N], Time, Par[N];
- ii RMQ[21][N*2];
- void DFS(int u, int p=-1){
- Start[u] = ++Time;
- RMQ[0][Time] = ii(Depth[u], u);
- for (int v : g[u]){
- if (v != p){
- Depth[v] = Depth[u] + 1;
- Par[v] = u;
- DFS(v, u);
- RMQ[0][++Time] = ii(Depth[u], u);
- }
- }
- }
- void Preprocess(){
- DFS(1);
- int LIM = log2(Time);
- for (int i = 1; i <= LIM; ++i){
- for (int j = 1; j + (1 << i) - 1 <= Time; ++j){
- RMQ[i][j] = min(RMQ[i-1][j], RMQ[i-1][j + (1 << (i-1))]);
- }
- }
- }
- int LCA(int u, int v){
- int Left = min(Start[u], Start[v]);
- int Right = max(Start[u], Start[v]);
- int len = log2(Right - Left + 1);
- return min(RMQ[len][Left], RMQ[len][Right - (1 << len) + 1]).se;
- }
- int ans = 0, vst[N];
- void fix(int u, int par){
- for(auto v : g[u]){
- if (v==par) continue;
- fix(v,u);
- vst[u] += vst[v];
- }
- if (vst[u]==0) ans++;
- }
- void proc()
- {
- Preprocess();
- cin >> m;
- for(int i=1; i<=m; i++){
- int u, v, z;
- cin >> u >> v;
- z = LCA(u,v);
- vst[u]++; vst[v]++;
- vst[z]--; vst[Par[z]]--;
- }
- fix(1,1);
- cout << ans;
- }
- signed main()
- {
- readfile();
- proc();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement