#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#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 sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const pi INF = {-MOD,MOD};
const int MX = 100001;
// #define LOCAL
#ifdef LOCAL
#else
#include "catdog.h"
#endif
// UTILITY
pi operator + (const pi& l, const pi& r) {
if (l == INF) return l;
return {l.f+r.f,l.s+r.s};
}
pi operator += (pi& l, const pi& r) { return l = l+r; }
pi operator + (const pi& l, const int& r) { return l+mp(r,r); }
pi operator += (pi& l, const int& r) { return l = l+r; }
pi operator - (const pi& l, const pi& r) {
if (l == INF) return l;
return {l.f-r.f,l.s-r.s};
}
pi operator -= (pi& l, const pi& r) { return l = l-r; }
pi comb(pi x, pi y) {
if (x == mp(-MOD,MOD)) return x;
return {min(x.f,y.f),max(x.s,y.s)};
}
pi neg(pi a) { return {-a.f,-a.s}; }
template<int SZ> struct L {
typedef pi T;
T dif[2*SZ], lazy[2*SZ]; // set SZ to a power of 2
L() {
memset (dif,0,sizeof dif);
memset (lazy,0,sizeof lazy);
}
void ad(int ind, pi x) {
lazy[ind] += x;
dif[ind] += x.f-x.s;
}
void push(int ind, int L, int R) {
if (L == R) return;
if (L != R) {
ad(2*ind,lazy[ind]);
ad(2*ind+1,lazy[ind]);
}
lazy[ind] = {0,0};
}
void pull(int ind) { dif[ind] = comb(dif[2*ind],dif[2*ind+1]); }
/*T query(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) { // get difference
push(ind,L,R);
if (lo > R || L > hi) return neg(INF);
if (lo <= L && R <= hi) return dif[ind];
int M = (L+R)/2;
return comb(query(lo,hi,2*ind,L,M), query(lo,hi,2*ind+1,M+1,R));
}*/
T getLazy(int x, int ind = 1, int L = 0, int R = SZ-1) { // OK
if (L == R) return lazy[ind];
push(ind,L,R);
int M = (L+R)/2;
if (x <= M) return getLazy(x,2*ind,L,M);
return getLazy(x,2*ind+1,M+1,R);
}
void upd(int lo, int hi, T inc, int ind = 1, int L = 0, int R = SZ-1) {
push(ind,L,R);
if (hi < L || R < lo) return;
if (lo <= L && R <= hi) {
ad(ind,inc);
push(ind,L,R);
return;
}
int M = (L+R)/2;
upd(lo,hi,inc,2*ind,L,M); upd(lo,hi,inc,2*ind+1,M+1,R);
pull(ind);
}
void adDif(int x, int z, int ind = 1, int L = 0, int R = SZ-1) { // TODO
if (x < L || x > R) return;
if (L == R) {
if (z == -1) {
dif[ind] = mp(0,0)+(lazy[ind].f-lazy[ind].s);
} else {
dif[ind] = INF;
}
return;
}
push(ind,L,R);
int M = (L+R)/2;
adDif(x,z,2*ind,L,M); adDif(x,z,2*ind+1,M+1,R);
pull(ind);
}
int getFst(int x, pi t, int ind = 1, int L = 0, int R = SZ-1) { // TODO
push(ind,L,R);
int M = (L+R)/2;
if (L == R) {
if (comb(t,dif[ind]) == t) return L;
return L+1;
}
if (x <= M) return getFst(x,t,2*ind,L,M);
if (x <= R) {
int tmp = getFst(x,t,2*ind+1,M+1,R);
if (tmp != M+1) return tmp;
return getFst(x,t,2*ind,L,M);
}
if (comb(t,dif[2*ind+1]) != t) return getFst(x,t,2*ind+1,M+1,R);
return getFst(x,t,2*ind,L,M);
/*
int tmp = getFst(x,t,2*ind+1,M+1,R);
if (tmp == M+1) return getFst(x,t,2*ind,L,M);
return tmp;*/
}
};
vector<vi> graph;
template <int V> struct HeavyLight { // sum queries, sum updates
int parent[V], heavy[V], depth[V];
int root[V], treePos[V], rTreePos[V];
L<V> val, child;
void init() {
int n = sz(graph)-1;
FOR(i,1,n+1) heavy[i] = -1;
parent[1] = -1, depth[1] = 0;
dfs(1);
for (int i = 1, currentPos = 0; i <= n; ++i)
if (parent[i] == -1 || heavy[parent[i]] != i)
for (int j = i; j != -1; j = heavy[j]) {
root[j] = i;
treePos[j] = currentPos;
rTreePos[currentPos] = treePos[j];
currentPos ++;
}
}
int dfs(int v) {
int size = 1, maxSubtree = 0;
for (auto u : graph[v]) if (u != parent[v]) {
parent[u] = v;
depth[u] = depth[v] + 1;
int subtree = dfs(u);
if (subtree > maxSubtree) heavy[v] = u, maxSubtree = subtree;
size += subtree;
}
return size;
}
template <class BinaryOperation>
void processPath(int u, int v, BinaryOperation op) {
for (; root[u] != root[v]; v = parent[root[v]]) {
if (depth[root[u]] > depth[root[v]]) swap(u, v);
op(treePos[root[v]], treePos[v]);
}
if (depth[u] > depth[v]) swap(u, v);
op(treePos[u], treePos[v]); // assumes values are stored in vertices
}
pi get(int x) { return val.getLazy(treePos[x]); }
void upd(int x, int y, pi z) {
if (y == 0) return;
// cout << "OH " << x << " " << y << "\n";
processPath(x,y,[this, &z](int l, int r) { val.upd(l,r,z); });
if (y != 1) {
//cout << "HI " << max(1,parent[x]) << " " << parent[y] << " " << z << "\n";
processPath(max(1,parent[x]),parent[y],[this, &z](int l, int r) { child.upd(l,r,z); });
//cout << child.getLazy(treePos[1]) << "\n";
}
}
void adDif(int v, int x) { child.adDif(treePos[v],x); }
int getFst(int v, pi x) { // TODO
int lst = v; v = parent[v];
while (v) {
int t = child.getFst(treePos[v],x);
if (t > treePos[root[v]]) {
if (t == treePos[v]+1) return lst;
// cout << "AH " << t << " " << rTreePos[t] << "\n";
return rTreePos[t];
}
lst = root[v]; v = parent[lst];
}
return 1;
}
};
HeavyLight<1<<17> H;
int N, st[MX];
pi trans(int v, pi x) {
switch(v) {
case 1: return {x.f,x.f+1};
case 2: return {x.s+1,x.s};
default:
x.s = min(x.s,x.f+1);
x.f = min(x.f,x.s+1);
return x;
}
}
int query() {
pi x = H.get(1);
return min(x.f,x.s);
}
void initialize(int n, std::vector<int> A, std::vector<int> B) {
N = n;
graph.resize(N+1);
F0R(i,N-1) graph[A[i]].pb(B[i]), graph[B[i]].pb(A[i]);
H.init();
}
pi eval(int v) { return trans(st[v],H.child.getLazy(H.treePos[v])); }
ostream& operator<<(ostream& o, const pi& x) {
o << x.f << " " << x.s << " | ";
return o;
}
void upd(int v, pi x) {
int m = min(x.f,x.s);
H.upd(1,v,{m,m});
x.f -= m, x.s -= m;
// cout << "TTT " << x << "\n";
if (x.f == 0 && x.s == 0) return;
int z;
if (x.f) {
z = H.getFst(v,{-1,0});
H.upd(z,v,{1,0});
} else {
z = H.getFst(v,{0,1});
H.upd(z,v,{0,1});
}
// cout << "TT " << v << " | " << x << " " << z << "\n";
// out << "OH " << z << " " << v << " " << x.f << " " << x.s << "\n";
if (z > 1) {
pi t = eval(H.parent[z])-H.get(H.parent[z]);
// cout << "HUH " << eval(H.parent[z]) << "\n";
if (t.f != t.s) {
cout << "BAD " << z << "\n" << eval(H.parent[z]) << "\n" << H.get(H.parent[z]) << "\n";
exit(0);
}
H.upd(1,H.parent[z],t);
}
}
int change(int ind, int v) {
// cout << "BEF " << H.get(v) << " " << neg(H.get(v)) << "\n";
upd(v,neg(H.get(v)));
//cout << "OOPS " << v << " " << H.get(v) << "\n";
if (st[v]) H.adDif(v,-1);
st[v] = ind;
if (st[v]) H.adDif(v,1);
upd(v,eval(v));
/*cout << "HI " << ind << " " << v << " " << eval(v) << "\n";
FOR(i,1,N+1) {
cout << H.get(i) << " " << H.child.getLazy(H.treePos[i]) << "\n";
}
cout << "\n";*/
pi x = H.get(1);
if (x.f < 0 || x.s < 0) {
// cout << H.get(2) << " " << " | " << H.get(1) << " " << "|" << " " << H.child.getLazy(1) << " " << eval(1) << "\n";
exit(0);
}
return min(x.f,x.s);
}
int cat(int v) { return change(1,v); }
int dog(int v) { return change(2,v); }
int neighbor(int v) { return change(0,v); }
#ifdef LOCAL
int readInt(){
int i;
if(scanf("%d",&i)!=1){
fprintf(stderr,"Error while reading input\n");
exit(1);
}
return i;
}
int main(){
int N=readInt();
std::vector<int> A(N-1),B(N-1);
for(int i=0;i<N-1;i++)
{
A[i]=readInt();
B[i]=readInt();
}
int Q;
assert(scanf("%d",&Q)==1);
std::vector <int> T(Q),V(Q);
for(int i=0;i<Q;i++)
{
T[i]=readInt();
V[i]=readInt();
}
initialize(N,A,B);
std::vector<int> res(Q);
for(int j=0;j<Q;j++)
{
if(T[j]==1) res[j]=cat(V[j]);
else if(T[j]==2) res[j]=dog(V[j]);
else res[j]=neighbor(V[j]);
if (res[j] < 0) cout << "AH " << j << " " << T[j] << " " << V[j] << "\n";
}
for(int j=0;j<Q;j++)
printf("%d\n",res[j]);
return 0;
}
#endif
/*
0
1
1
2
1
*/
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
8532 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
8680 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
8532 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
8680 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
8532 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
8680 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
