This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
const ll N = 3e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 350;
ll n,m,q,timer=0;
vector<ll>adj[N];
ll up[N][20], d[N], tin[N], a[N];
void pre_dfs(ll u, ll par){
tin[u] = ++timer;
for(auto v : adj[u]){
if(v == par) continue;
up[v][0] = u;
for(int i = 1; i <= 19;i++) up[v][i] = up[up[v][i-1]][i-1];
d[v] = d[u] + 1;
pre_dfs(v, u);
}
}
ll lca(ll u, ll v){
if(d[u] != d[v]){
if(d[u] < d[v]) swap(u, v);
ll k = d[u] - d[v];
for(int i = 19; i >= 0;i--) if(k & (1 << i)) u = up[u][i];
}
if(u == v) return u;
for(int i = 19; i >= 0;i--) if(up[u][i] != up[v][i]) u = up[u][i], v = up[v][i];
return up[u][0];
}
ll dist(ll u, ll v){return d[u] + d[v] - 2 * d[lca(u, v)];}
void to_thic_cau(){
cin >> n >> m >> q;
for(int i = 1; i <= n - 1;i++){
ll u,v; cin >> u >> v;
adj[u].pb(v); adj[v].pb(u);
}
pre_dfs(1, 0);
for(int i = 1; i <= m;i++) cin >> a[i];
while(q--){
ll l,r; cin >> l >> r;
vector<ll>v;
for(int i = l; i <= r;i++) v.pb(a[i]);
sort(all(v), [&](const ll &a, const ll&b){
return tin[a] < tin[b];
});
ll res = 0;
for(int i = 1; i < v.size();i++) res += dist(v[i], v[i-1]);
res += dist(v[0], v.back());
res /= 2;
cout << res + 1 << '\n';
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll tc = 1;
//cin >> tc;
while(tc--) to_thic_cau();
}
Compilation message (stderr)
tourism.cpp: In function 'void to_thic_cau()':
tourism.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int i = 1; i < v.size();i++) res += dist(v[i], v[i-1]);
| ~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |