#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
using namespace std;
using namespace __gnu_pbds;
/*
ll add(ll x,ll y){
x+=y;
if(x<0){
x%=mod;
x+=mod;
}else{
if(x>=mod) x%=mod;
}
return x;
}
ll mul(ll a,ll b){
ll ans = (a*b)%mod;
if(ans<0) ans+=mod;
return ans;
}
*/
typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
return uniform_int_distribution<ll>(l,r)(rng);
}
#define maxn 100005
#define lg 18
ll n,m,q;
vector<ll> g[maxn];
pll edge[maxn];
ll in[maxn];
ll t[4*maxn];
ll a[maxn];
ll c[maxn];
ll up[maxn];
ll sub[maxn];
ll st[maxn][lg];
bool tu[maxn];
ll timer = 0;
void upd(ll v,ll tl,ll tr,ll i,ll x){
if(tl==tr){t[v] = x;return;}
ll mid = (tl+tr)/2;
if(i<=mid) upd(2*v,tl,mid,i,x);
else upd(2*v+1,mid+1,tr,i,x);
t[v] = t[2*v] + t[2*v+1];
}
ll sum(ll v,ll tl,ll tr,ll l,ll r){
if(l>r) return 0;
if(tl==l&&tr==r) return t[v];
ll mid = (tl+tr)/2;
return sum(2*v,tl,mid,l,min(mid,r)) + sum(2*v+1,mid+1,tr,max(mid+1,l),r);
}
void init(ll v,ll tl,ll tr){
if(tl==tr){
t[v] = 1;
return;
}
ll mid = (tl+tr)/2;
init(2*v,tl,mid); init(2*v+1,mid+1,tr);
t[v] = t[2*v] + t[2*v+1];
}
void dfs_siz(ll u,ll par){
sub[u] = 1; st[u][0] = par;
for(ll s : g[u]) if(s!=par) dfs_siz(s,u),sub[u]+=sub[s];
}
void dfs(ll u,ll par,ll last){
up[u] = last;
in[u] = ++timer;
ll smax = 0;
for(ll s : g[u]){
if(s==par) continue;
if(sub[s]>sub[smax]) smax = s;
}
if(smax!=0) dfs(smax,u,last);
for(ll s : g[u]){
if(s==par||s==smax) continue;
dfs(s,u,s);
}
}
ll root(ll u){
if(sum(1,1,n,in[u],in[u])) return u;
ll v = up[u];
ll cur = sum(1,1,n,in[v],in[u]);
while(!cur&&u!=1){
if(sum(1,1,n,in[u],in[u])) return u;
u = st[v][0]; v = up[u]; cur = sum(1,1,n,in[v],in[u]);
}
if(sum(1,1,n,in[u],in[u])) return u;
ll ans = u;
for(ll j = lg-1;j>=0;j--){
if(in[st[ans][j]]<in[v]) continue;
if(sum(1,1,n,in[st[ans][j]],in[u])==0) ans = st[ans][j];
}
return st[ans][0];
}
int main(){
daj_mi_malo_vremena
cin >> n >> m >> q;
fill(a+1,a+n+1,1);
for(ll i = 1;i<=n-1;i++){
ll &x = edge[i].fi; ll &y = edge[i].sc;
cin >> x >> y;
g[x].pb(y);
g[y].pb(x);
}
dfs_siz(1,1); dfs(1,1,1);
init(1,1,n);
while(m--){
ll i; cin >> i;
ll x = edge[i].fi; ll y = edge[i].sc;
if(in[x]>in[y]) swap(x,y);
if(tu[i]){
a[y] = c[y] = a[root(y)];
upd(1,1,n,in[y],1);
tu[i] = 1;
}else{
a[root(x)] += a[y] - c[y];
upd(1,1,n,in[y],0);
tu[i] = 1;
}
}
while(q--){
ll x; cin >> x;
cout<<a[root(x)]<<endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2772 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
32440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
234 ms |
36832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
