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 F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
const ll mxN=1e5+5;
const ll inf=1e18;
vector<pll> adj[mxN];
vector<pll> tim[mxN];
vll tep[mxN];
ll n, m, q;
ll dfs(ll cur, ll edge, ll par, ll mx){
if(par!=-1 && (tim[edge].empty() || tim[edge][0].F>=mx)){
return 0;
}
pll it={inf, inf};
if(par!=-1)
it=*prev(upper_bound(tim[edge].begin(), tim[edge].end(), make_pair(mx, 0LL)));
mx=min(mx, it.S);
ll re=1;
for(auto &[x, y]:adj[cur]){
if(x==par) continue;
re+=dfs(x, y, cur, mx);
}
return re;
}
void solve(){
cin>>n>>m>>q;
for(ll i=1;i<=n-1;i++){
ll a, b;
cin>>a>>b;
adj[a].pb({b, i});
adj[b].pb({a, i});
}
for(ll i=0;i<m;i++){
ll a;
cin>>a;
tep[a].pb(i);
}
for(ll i=1;i<=n-1;i++){
if(tep[i].size()%2==1){
tep[i].pb(m);
}
}
for(ll i=1;i<=n-1;i++){
for(ll j=0;j<tep[i].size();j+=2){
tim[i].pb({tep[i][j], tep[i][j+1]});
}
}
for(ll rep=0;rep<q;rep++){
ll tar;
cin>>tar;
cout<<dfs(tar, 0, -1, inf)<<'\n';
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
Compilation message (stderr)
synchronization.cpp: In function 'void solve()':
synchronization.cpp:54:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(ll j=0;j<tep[i].size();j+=2){
| ~^~~~~~~~~~~~~~
# | 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... |