#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;
/*
` '
;,,, ` ' ,,,;
`Y3S3333bo. : : .od3333Y3S'
3331O3D033b. : : .d333313D033
3L0V3Y' `Y3b. ` ' .d3Y' `YL0V33
jTH33! .db. Yb. ' ' .dY .db. 3TH33!
`333 Y33Y `b ( ) d' Y33Y 333'
3MYb '" ,', "' dMY3
j3pr3C10USgf"' ':' `"?g3pr3C10USk
'Y' .3' d' 'b '3. 'Y'
! .3' db d'1 1`b db '3. !
d33 `' 3 ; ; 3 `' 33b
d331b .g8 ',' 8g. d133b
:333LOV333Y' 'Y33L0V3333:
'! TH33333' `333TH33 !'
'3Y `Y Y' Y3'
Y Y
! !
*/
using ll = long long;
using db = long double;
using str = string;
// pairs
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
#define mt make_tuple
#define mp make_pair
#define ff first
#define ss second
// vector
template<class T> using V = vector<T>;
using vi = V<int>;
using vl = V<ll>;
using vd = V<db>;
using vb = V<bool>;
using vpi = V<pi>;
using vpl = V<pl>;
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(a) (int)((a).size())
#define ini(a, b) memset(a, b, sizeof(a))
#define rsz resize
#define pb push_back
#define eb emplace_back
#define ins insert
#define arr array
#define lb lower_bound
#define ub upper_bound
template<class T> int lwb(V<T>& a, const T& b) { return (int)(lb(all(a), b)-a.begin()); }
template<class T> int upb(V<T>& a, const T& b) { return (int)(ub(all(a), b)-a.begin()); }
// loops
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto& a : x)
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up ceil()
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down floor()
// consts
const int MOD = (int)1e9+7; // 998244353;
const int INF = (int)0x3f3f3f3f; // INF+INF < INF_MAX
const ll INFL = ll(0x3f3f3f3f3f3f3f3f); // INFL+INFL < LLONG_MAX
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
// statement
const int maxn=100000;
int N, M, Q, info[maxn], Cinfo[maxn];
bool A[maxn];
pi edge[maxn];
vi adj[maxn];
//hld
int par[4*maxn], ssz[maxn];
int Tm, pos[maxn], anc[maxn], flat[maxn], heavy[maxn];
void dfs_sz(int p, int s) {
par[s]=p;
ssz[s]=info[s]=1;/*
if(sz(adj[s])>=2&&adj[s][0]==p)
swap(adj[s][0], adj[s][1]);*/
trav(u, adj[s]) if(u!=p) {
dfs_sz(s, u);
ssz[s]+=ssz[u];/*
if(ssz[adj[s][0]]<ssz[u])
swap(adj[s][0], u);*/
if(heavy[s]==-1||ssz[heavy[s]]<ssz[u])
heavy[s]=u;
}
}
/*
int init(int p, int u) {
ssz[u] = 1;
info[u] = 1;
par[u] = p;
for (int v : adj[u]) {
if (v == p) continue;
ssz[u] += init(u, v);
if (heavy[u] == -1 || ssz[v] > ssz[heavy[u]]) {
heavy[u] = v;
}
}
return ssz[u];
}*/
void build_hld(int p, int u, int r) {
anc[u] = r;
pos[u] = Tm;
flat[Tm] = u;
++Tm;
if(Tm<0)
exit(1);
if (heavy[u] == -1)
return;
build_hld(u, heavy[u], r);
for (int v : adj[u]) {
if (v == p || v == heavy[u]) continue;
build_hld(u, v, v);
}
}
/*
void build_hld(int s) {
pos[s]=Tm;
flat[Tm]=s;
++Tm;
trav(u, adj[s]) if(u!=par[s]) {
if(u==adj[s][0])
anc[u]=anc[s];
else
anc[u]=u;
build_hld(u);
}
}*/
//segment tree
int st[maxn];
bool __[maxn];
#define tm ((tl+tr)/2)
#define lv (2*v+1)
#define rv (2*v+2)
void build_st(int v, int tl, int tr) {
if(tl==tr)
st[v]=flat[tl];
else {
build_st(lv, tl, tm);
build_st(rv, tm+1, tr);
st[v]=st[rv];
}
}
void update(int v, int tl, int tr, int ind) {
if(tl==tr) {
__[tl]^=1;
st[v]=(__[tl]?-1:flat[tl]);
} else {
if(ind<=tm)
update(lv, tl, tm, ind);
else
update(rv, tm+1, tr, ind);
st[v]=st[(st[rv]==-1?lv:rv)];
}
}
int query(int v, int tl, int tr, int l, int r) {
if(tl==l&&tr==r)
return st[v];
if(r<=tm)
return query(lv, tl, tm, l, r);
if(l>tm)
return query(rv, tm+1, tr, l, r);
int o=query(rv, tm+1, tr, tm+1, r);
if(o==-1)
return query(lv, tl, tm, l, tm);
return o;
}
int q(int s) {
int res=-1;
while(res==-1&&s!=-1) {
res=query(0, 0, N-1, pos[anc[s]], pos[s]);
s=par[anc[s]];
}
return res;
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
ini(heavy, -1);
cin >> N >> M >> Q;
F0R(i, N-1) {
int U, V; cin >> U >> V;
--U; --V;
edge[i]=mp(U, V);
adj[U].pb(V);
adj[V].pb(U);
}
dfs_sz(-1, 0);
build_hld(-1, 0, 0);
build_st(0, 0, N-1);
F0R(i, M) {
int D, U, V; cin >> D;
--D;
tie(U, V)=edge[D];
if(par[U]==V)
swap(U, V);
if(!A[D])
info[q(U)]+=info[V]-Cinfo[V];
else
info[V]=Cinfo[V]=info[q(U)];
update(0, 0, N-1, pos[V]);
A[D]^=1;
}
F0R(i, Q) {
int C; cin >> C;
--C;
cout << info[q(C)] << '\n';
}
return 11^3^1<<3;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3028 KB |
Output is correct |
| 2 |
Correct |
1 ms |
3028 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3028 KB |
Output is correct |
| 4 |
Correct |
1 ms |
3028 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3028 KB |
Output is correct |
| 6 |
Correct |
3 ms |
3156 KB |
Output is correct |
| 7 |
Correct |
13 ms |
3928 KB |
Output is correct |
| 8 |
Correct |
13 ms |
3900 KB |
Output is correct |
| 9 |
Correct |
13 ms |
3932 KB |
Output is correct |
| 10 |
Correct |
169 ms |
10396 KB |
Output is correct |
| 11 |
Incorrect |
146 ms |
10400 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
13236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3028 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3028 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3028 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3028 KB |
Output is correct |
| 5 |
Correct |
1 ms |
3028 KB |
Output is correct |
| 6 |
Correct |
3 ms |
3156 KB |
Output is correct |
| 7 |
Correct |
14 ms |
4676 KB |
Output is correct |
| 8 |
Incorrect |
162 ms |
16672 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
145 ms |
16748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3028 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3028 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3028 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3028 KB |
Output is correct |
| 5 |
Correct |
3 ms |
3156 KB |
Output is correct |
| 6 |
Correct |
15 ms |
3936 KB |
Output is correct |
| 7 |
Incorrect |
191 ms |
10784 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
