| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P153PROH - ROUND 3H - Phòng họp |
PTIT đang trong mùa thi, Tí và Tèo đang căng sức học cho các môn ở năm 3, các cậu phải thi trong m ngày mỗi ngày thi ở một phòng, sau khi thi xong các cậu muốn gặp nhau ở cùng một phòng để cùng thảo luận về bài thi của mình, và phòng họp chung đó phải cách đều 2 phòng mà Tí và Tèo thi. Ở PTIT có n phòng, đánh số từ 1 đến n, các phòng được nối với nhau bởi n – 1 hành lang, 2 phòng bắt kì luôn có thể qua lại trực tiếp hoặc đi qua một số phòng trung gian.
Các bạn hãy giúp Tí và Tèo đếm xem trong mỗi ngày thi có bao nhiêu phòng có thể dùng làm phòng thảo luận của 2 cậu.
Input
Dòng thứ nhất chứa số nguyên n(1 <= n <= 10^5) – Số phòng của PTIT.
n – 1 dòng tiếp theo chứa cặp số a[i] và b[i] (1 <= i <= n – 1, 1 <= a[i], b[i] <= n) thể hiện có hành lang nối giữa phòng a[i] và phòng b[i].
Dòng tiếp theo chứa số nguyên m(1 <= m <= 10^5) – Số ngày thi của Tí và Tèo.
m dòng tiếp mỗi dòng chứa cặp số x[i], y[i] (1 <= i <= m, 1 <= x[i], y[i] <= n), x[i] là phòng thi của Tí vào ngày i, y[i] là phòng thi của Tèo vào ngày i.
Output
Gồm m dòng, mỗi dòng chứa số phòng có thể dùng làm thảo luận của ngày thi tương ứng.
Example
Test 1:
Input:
4
1 2
1 3
2 4
1
2 3
Output:
1
Test 2:
Input:
4
1 2
2 3
2 4
2
1 2
1 3
Output:
0
2
| Được gửi lên bởi: | adm |
| Ngày: | 2015-03-19 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2024-08-01 10:43:55
code : #include <bits/stdc++.h> #define fo(i, d, c) for (int i = d; i <= c; i++) #define fod(i, c, d) for (int i = c; i >= d; i--) #define maxn 1000010 #define N 1010 #define fi first #define se second #define pb emplace_back #define en cout << "\n"; #define int long long #define inf (int)1e18 #define bitcount(x) __builtin_popcountll(x) #define pii pair<int, int> #define vii vector<pii> #define lb(x) x & -x #define bit(i, j) ((i >> j) & 1) #define offbit(i, j) (i ^ (1LL << j)) #define onbit(i, j) (i | (1LL << j)) #define vi vector<int> #define all(x) x.begin(), x.end() #define ss(x) (int)x.size() template <typename T1, typename T2> bool minimize(T1 &a, T2 b) { if (a > b) { a = b; return true; } return false; } template <typename T1, typename T2> bool maximize(T1 &a, T2 b) { if (a < b) { a = b; return true; } return false; } using namespace std; const int nsqrt = 450; const int mod = 1e9 + 7; void add(int &x, int k) { x += k; x %= mod; if(x < 0) x += mod; } void del(int &x, int k) { x -= k; x %= mod; if(x < 0) x += mod; } int n; vi ke[maxn]; int h[maxn],par[maxn][20]; int sz[maxn]; void dfs(int u) { sz[u] = 1; for(int v : ke[u]) if(v != par[u][0]) { h[v] = h[u] + 1; par[v][0] = u; fo(i,1,19) par[v][i] = par[par[v][i - 1]][i - 1]; dfs(v); sz[u] += sz[v]; } } int lca(int u, int v) { if (h[u] < h[v]) swap(u, v); int del = h[u] - h[v]; fod(i, 19, 0) if (bit(del, i)) u = par[u][i]; if (u == v) return u; fod(i, 19, 0) if (par[u][i] != par[v][i]) u = par[u][i], v = par[v][i]; return par[u][0]; } int dist(int u,int v) { return h[u] + h[v] - 2 * h[lca(u,v)]; } int findpar(int u,int dist) { fod(i,19,0) if(bit(dist,i)) u = par[u][i]; return u; } main() { #define name "TASK" if (fopen(name ".inp", "r")) { freopen(name ".inp", "r", stdin); freopen(name ".out", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; fo(i,1,n - 1) { int u,v; cin >> u >> v; ke[u].pb(v); ke[v].pb(u); } dfs(1); int q; cin >> q; while(q--) { int a,b; cin >> a >> b; int x = dist(a,b); int l = lca(a,b); if(dist(a,l) < dist(b,l)) swap(a,b); if(a == b) cout << n; else if(x % 2 == 1) cout << 0; else { if(dist(a,l) == x / 2) cout << n - sz[findpar(a,x / 2 - 1)] - sz[findpar(b,x / 2 - 1)]; else { cout << sz[findpar(a,x / 2)] - sz[findpar(a,x / 2 - 1)]; } } en; } } |
|
|
2015-10-22 05:04:48 bembembem
admin add thêm ngôn ngữ pascal được không ạ ? Last edit: 2015-10-22 05:05:06 |
