#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define p(x,y) pair<ll,ll>(x,y)
#define BIT(i,x) ((x>>i)&1)
#define MASK(x) (1<<x)
#define ld long double
#define __builtin_popcount __builtin_popcountll
#define pll pair<ll,ll>
#define kt cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n"
template<class T1,class T2>
bool maximize(T1 &x,T2 y)
{
if(x<y)
{
x=y;
return 1;
}
return 0;
}
template<class T1,class T2>
bool minimize(T1 &x,T2 y)
{
if(y<x)
{
x=y;
return 1;
}
return 0;
}
const ll M=1e9+9;
template <class T1,class T2>
void add(T1 &x,T2 y)
{
x+=y;
if(x>=M) x-=M;
}
template <class T1,class T2>
void sub(T1 &x, T2 y)
{
x-=y;
if(x<0) x+=M;
}
void online()
{
std::ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef thuc
freopen("input.inp","r",stdin);
freopen("output.out","w",stdout);
#else
#endif // thuc
}
const ll N=200100;
vector<ll> gr[N];
ll c[N],par[N][20],heavy[N],head[N],in[N],cnt,Tree[4*N],vl[N],lst[N],n,q,m;
ll U[N],V[N];
void dfs(ll u)
{
c[u]=1;
for(auto v:gr[u])
{
if(v==par[u][0]) continue;
par[v][0]=u;
dfs(v);
c[u]+=c[v];
if(c[heavy[u]]<c[v])
{
heavy[u]=v;
}
}
}
void decompose(ll u,ll h)
{
head[u]=h;
in[u]=++cnt;
if(heavy[u])
{
decompose(heavy[u],h);
}
for(auto v:gr[u])
{
if(v==par[u][0]||v==heavy[u]) continue;
decompose(v,v);
}
}
ll update(ll i,ll l,ll r,ll pos,ll vl)
{
if(r<pos||pos<l) return Tree[i];
if(l==r) return Tree[i]=vl;
return Tree[i]=update(i*2,l,(l+r)/2,pos,vl)&update(i*2+1,(l+r)/2+1,r,pos,vl);
}
ll query(ll i,ll l,ll r,ll l1,ll r1)
{
if(r1<l||r<l1) return 1;
if(l1<=l&&r<=r1) return Tree[i];
return query(i*2,l,(l+r)/2,l1,r1)&query(i*2+1,(l+r)/2+1,r,l1,r1);
}
ll root(ll u)
{
while(u!=1)
{
if(!query(1,1,n,in[head[u]],in[u])) break;
u=par[head[u]][0];
}
for(int i=18;i>=0;i--)
{
if(head[par[u][i]]==head[u])
{
if(query(1,1,n,in[par[u][i]],in[u])) u=par[par[u][i]][0];
}
}
if(query(1,1,n,in[u],in[u])) u=par[u][0];
return u;
}
ll change(ll i)
{
ll u=root(U[i]),v=root(V[i]);
if(v==V[i])
{
update(1,1,n,in[v],1);
vl[u]=vl[v]+vl[u]-lst[i];
}
else
{
update(1,1,n,in[V[i]],0);
lst[i]=vl[u];
vl[root(V[i])]=vl[u];
}
}
int main()
{
online();
cin>>n>>m>>q;
for(int i=1;i<n;i++)
{
ll u,v;
cin>>u>>v;
U[i]=u;
V[i]=v;
gr[u].emplace_back(v);
gr[v].emplace_back(u);
}
dfs(1);
decompose(1,1);
for(int i=1;i<n;i++)
{
if(V[i]==par[U[i]][0])
{
swap(U[i],V[i]);
}
}
for(int i=1;i<=18;i++)
{
for(int j=1;j<=n;j++)
{
par[j][i]=par[par[j][i-1]][i-1];
}
}
for(int i=1;i<=n;i++)
{
vl[i]=1;
}
for(int i=1;i<=m;i++)
{
ll x;
cin>>x;
change(x);
}
for(int i=1;i<=q;i++)
{
ll u;
cin>>u;
cout<<vl[root(u)]<<'\n';
}
kt;
}
Compilation message
synchronization.cpp: In function 'long long int change(long long int)':
synchronization.cpp:132:1: warning: no return statement in function returning non-void [-Wreturn-type]
132 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
32348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
69 ms |
82384 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
32216 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
77 ms |
90408 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
32348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
