#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];
void dfs_sz(int s, int p) {
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(u, s);
ssz[s]+=ssz[u];
if(ssz[adj[s][0]]<ssz[u])
swap(adj[s][0], u);
}
}
void build_hld(int s) {
flat[pos[s]=Tm++]=s;
trav(u, adj[s]) if(u!=par[s]) {
anc[u]=(u==adj[s][0]?anc[s]: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 o;
return query(lv, tl, tm, l, tm);
}
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==-1?0:res);
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
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(0, -1);
build_hld(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 |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2732 KB |
Output is correct |
| 7 |
Correct |
12 ms |
3444 KB |
Output is correct |
| 8 |
Correct |
12 ms |
3540 KB |
Output is correct |
| 9 |
Correct |
11 ms |
3548 KB |
Output is correct |
| 10 |
Execution timed out |
8077 ms |
9368 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8013 ms |
13452 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 7 |
Correct |
14 ms |
4308 KB |
Output is correct |
| 8 |
Execution timed out |
8085 ms |
17088 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8052 ms |
17140 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 6 |
Correct |
16 ms |
3540 KB |
Output is correct |
| 7 |
Execution timed out |
8016 ms |
9400 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
