#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
#include<complex>
#include<time.h>
#include<cassert>
#include<functional>
#include<numeric>
#include<tuple>
using namespace std;
using ll = long long;
using ld = long double;
using H = pair<ll, ll>;
using P = pair<ll, H>;
using vi = vector<ll>;
#define all(a) (a).begin(),(a).end()
#define fs first
#define sc second
#define xx first
#define yy second.first
#define zz second.second
#define Q(i,j,k) mkp(i,mkp(j,k))
#define rng(i,s,n) for(ll i = (s) ; i < (n) ; i++)
#define rep(i,n) rng(i, 0, (n))
#define mkp make_pair
#define vec vector
#define pb emplace_back
#define siz(a) (int)(a).size()
#define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end())
#define getidx(b,num) (lower_bound(all(b),(num))-(b).begin())
#define ssp(i,n) (i==(ll)(n)-1?"\n":" ")
#define ctoi(c) (int)(c-'0')
#define itoc(c) (char)(c+'0')
#define cyes printf("Yes\n")
#define cno printf("No\n")
#define cdf(n) for(int quetimes_=(n);quetimes_>0;quetimes_--)
#define gcj printf("Case #%lld: ",qq123_+1)
#define readv(a,n) a.resize(n,0);rep(i,(n)) a[i]=read()
#define found(a,x) (a.root(x)!=a.end())
constexpr ll mod = (ll)1e9 + 7;
constexpr ll Mod = 998244353;
constexpr ld EPS = 1e-10;
constexpr ll inf = (ll)3 * 1e18;
constexpr int Inf = (ll)15 * 1e8;
constexpr int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
ll read() { ll u, k = scanf("%lld", &u); return u; }
string reads() { string s; cin >> s; return s; }
H readh(short g = 0) { H u; int k = scanf("%lld %lld", &u.fs, &u.sc); if (g == 1) u.fs--, u.sc--; if (g == 2) u.fs--; return u; }
bool ina(H t, int h, int w) { return 0 <= t.fs && t.fs < h && 0 <= t.sc && t.sc < w; }
bool ina(int t, int l, int r) { return l <= t && t < r; }
ll gcd(ll i, ll j) { return j ? gcd(j, i % j) : i; }
ll ppc(ll x) {
int sum = 0; for (int i = 0; i < 60; i++)if ((1ll << i) & x) sum++;
return sum;
}
void fin1() { printf("-1\n"); exit(0); }
void fin0() { printf("0\n"); exit(0); }
template<typename T>
class csum {
vec<T> v;
public:
csum(vec<T>& a) :v(a) { build(); }
csum() {}
csum(int sz) { init(sz); }
void init(int sz) { v = vector<T>(sz, 0); }
void init(vec<T>& a) { v = a; build(); }
void build() {
for (int i = 1; i < v.size(); i++) v[i] += v[i - 1];
}
void add(int l, int r, T x) {
v[l] += x;
v[r] -= x;
}//[l,r)
//[l,r]
T a(int l, int r) {
if (r < l) return 0;
return v[r] - (l == 0 ? 0 : v[l - 1]);
}
//[l,r)
T b(int l, int r) {
return a(l, r - 1);
}
T a(pair<int, int>t) {
return a(t.first, t.second);
}
T b(pair<int, int>t) {
return b(t.first, t.second);
}
T operator[](int x)const {
return v[x];
}
};
template<ll mod>
class modint {
public:ll v;
modint(ll v = 0) { s(v % mod + mod); }
constexpr static int fn_ = (ll)2e6 + 5;
static vector<modint>fact, comp;
modint pow(ll x) const {
modint b(v), c(1);
while (x) {
if (x & 1) c *= b;
b *= b;
x >>= 1;
}
return c;
}
inline modint& s(int vv) {
v = vv < mod ? vv : vv - mod;
return *this;
}
inline modint inv()const { return pow(mod - 2); }
inline modint operator-()const { return modint() - *this; }
inline modint& operator+=(const modint b) { return s(v + b.v); }
inline modint& operator-=(const modint b) { return s(v + mod - b.v); }
inline modint& operator*=(const modint b) { v = v * b.v % mod; return *this; }
inline modint& operator/=(const modint b) { v = v * b.inv().v % mod; return *this; }
inline modint operator+(const modint& b) const { return modint(v) += b; }
inline modint operator-(const modint& b) const { return modint(v) -= b; }
inline modint operator*(const modint& b) const { return modint(v) *= b; }
inline modint operator/(const modint& b) const { return modint(v) /= b; }
friend ostream& operator<<(ostream& os, const modint& m) {
return os << m.v;
}
friend istream& operator>>(istream& is, modint& m) {
int x; is >> x; m = modint(x);
return is;
}
bool operator<(const modint& r)const { return v < r.v; }
bool operator>(const modint& r)const { return v > r.v; }
bool operator<=(const modint& r)const { return v <= r.v; }
bool operator>=(const modint& r)const { return v >= r.v; }
bool operator==(const modint& r)const { return v == r.v; }
bool operator!=(const modint& r)const { return v != r.v; }
explicit operator bool()const { return v; }
explicit operator int()const { return v; }
modint comb(modint k) {
if (k > *this) return modint();
if (fact.empty()) combinit();
if (v >= fn_) {
if (k > *this - k) k = *this - k;
modint tmp(1);
for (int i = v; i >= v - k.v + 1; i--) tmp *= modint(i);
return tmp * comp[k.v];
}
return fact[v] * comp[k.v] * comp[v - k.v];
}//nCk
modint perm(modint k) {
if (k > *this) return modint();
if (fact.empty()) combinit();
if (v >= fn_) {
modint tmp(1);
for (int i = v; i >= v - k.v + 1; i--) tmp *= modint(i);
return tmp;
}
return fact[v] * comp[v - k.v];
}//nPk
static void combinit() {
fact.assign(fn_, modint());
fact[0] = 1;
for (int i = 1; i < fn_; i++) fact[i] = fact[i - 1] * modint(i);
comp.assign(fn_, modint());
comp[fn_ - 1] = fact[fn_ - 1].inv();
for (int i = fn_ - 2; i >= 0; i--) comp[i] = comp[i + 1] * modint(i + 1);
}
};
using mint = modint<ll(1e9 + 7)>; template<>vec<mint> mint::fact = vec<mint>(); template<>vec<mint> mint::comp = vec<mint>();
//--------------------------------------------------------------
class unionfind {
int size = 0, grps = 0;
vector<int>pa;
public:
unionfind() {}
unionfind(int n) {
init(n);
}
void init(int n) {
size = n, grps = n;
pa.assign(n + 1, -1);
}
int root(int x) {
if (pa[x] < 0) return x;
return pa[x] = root(pa[x]);
}
bool unite(int x, int y) {
x = root(x); y = root(y);
if (x == y) return false;
grps--;
if (pa[x] > pa[y]) swap(x, y);
pa[x] += pa[y];
pa[y] = x;
return true;
}
bool same(int x, int y) {
return root(x) == root(y);
}
bool isroot(int x) {
return x == root(x);
}
int sz(int x) {
return -pa[root(x)];
}
int groups() {
return grps;
}
H operator[](int x) {
x = root(x);
return H{ x,-pa[x] };
}
};
//--------------------------------------------------------------
struct A {
int a, b;
};
int n, m, q;
vec<int>e[200000];
vec<A>edg;
int dp[200000];
int sz[200000];
int in[200000], idx;
int out[200000];
int head[200000];
int dpt[200000], par[200000];
void dfs_sz(int v, int p, int d) {
sz[v] = 1;
par[v] = p;
dpt[v] = d;
if (e[v][0] == p) swap(e[v][0], e[v].back());
for (auto& g : e[v]) {
if (g == p) continue;
dfs_sz(g, v, d + 1);
sz[v] += sz[g];
if (sz[g]>sz[e[v][0]]) swap(g, e[v][0]);
}
}
void dfs_hld(int v, int p) {
out[idx] = v;
in[v] = idx++;
for (auto g : e[v]) {
if (g == p) continue;
head[g] = (g == e[v][0] ? head[v] : g);
dfs_hld(g, v);
}
}
int dat[200000];
void add(int x, int v) {
x++;
while (x <= idx) {
dat[x] += v;
x += x&-x;
}
}
int sum1(int x) {
x++;
int sum = 0;
while (x>0) {
sum += dat[x];
x -= x&-x;
}
return sum;
}
int sum(int l, int r) {
return sum1(r - 1) - sum1(l - 1);
}
int lb(int l, int r) {
int ok = l, ng = r, mid;
while (ng - ok>1) {
mid = (ok + ng) / 2;
if (sum(mid, r)>0) ok = mid;
else ng = mid;
}
return ok;
}
void add_hld(int l, int r, int x) {
if (dpt[l]>dpt[r]) swap(l, r);
add(in[r], x);
}
int fst_hld(int x) {
while (head[x] != 0) {
if (sum(in[head[x]], in[x] + 1)>0) {
return out[lb(in[head[x]], in[x] + 1)];
}
x = par[head[x]];
}
if (sum(in[head[x]], in[x] + 1)>0) {
return out[lb(in[head[x]], in[x] + 1)];
}
return 0;
}//さかのぼっていく途中で、初めて値がついている辺はどこだ？
signed main() {
cin >> n >> m >> q;
rep(i, n - 1) {
int u, v; cin >> u >> v;
u--; v--;
e[u].pb(v);
e[v].pb(u);
edg.pb(A{ u,v });
}
dfs_sz(0, -1, 0); dfs_hld(0, -1);
rep(i, n - 1) {
if (dpt[edg[i].a]>dpt[edg[i].b]) {
swap(edg[i].a, edg[i].b);
}
}
for (auto g : edg) {
add_hld(g.a, g.b, 1);
}
vec<bool>b(n, 0);
vec<int>c(n, 0);
rep(i, n) dp[i] = 1;
rep(i, m) {
int d; cin >> d;
d--;
b[d] = !b[d];
if (b[d]) {
int t = fst_hld(par[edg[d].b]);
dp[t] += dp[edg[d].b] - c[edg[d].b];
add_hld(edg[d].a, edg[d].b, -1);
}
else {
int t = fst_hld(edg[d].b);
dp[edg[d].b] = dp[t];
c[edg[d].b] = dp[edg[d].b];
add_hld(edg[d].a, edg[d].b, 1);
}
}
rep(i, q) {
int v; cin >> v;
v--;
cout << dp[fst_hld(v)] << endl;
}
}
Compilation message
synchronization.cpp: In function 'll read()':
synchronization.cpp:69:19: warning: unused variable 'k' [-Wunused-variable]
69 | ll read() { ll u, k = scanf("%lld", &u); return u; }
| ^
synchronization.cpp: In function 'H readh(short int)':
synchronization.cpp:71:33: warning: unused variable 'k' [-Wunused-variable]
71 | H readh(short g = 0) { H u; int k = scanf("%lld %lld", &u.fs, &u.sc); if (g == 1) u.fs--, u.sc--; if (g == 2) u.fs--; return u; }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 6 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 7 |
Correct |
20 ms |
5996 KB |
Output is correct |
| 8 |
Correct |
20 ms |
5996 KB |
Output is correct |
| 9 |
Correct |
20 ms |
5996 KB |
Output is correct |
| 10 |
Correct |
256 ms |
15072 KB |
Output is correct |
| 11 |
Correct |
254 ms |
14944 KB |
Output is correct |
| 12 |
Correct |
285 ms |
24288 KB |
Output is correct |
| 13 |
Correct |
155 ms |
14808 KB |
Output is correct |
| 14 |
Correct |
193 ms |
14432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
148 ms |
19424 KB |
Output is correct |
| 2 |
Correct |
146 ms |
19296 KB |
Output is correct |
| 3 |
Correct |
169 ms |
23648 KB |
Output is correct |
| 4 |
Correct |
168 ms |
23648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 6 |
Correct |
11 ms |
5228 KB |
Output is correct |
| 7 |
Correct |
52 ms |
7020 KB |
Output is correct |
| 8 |
Correct |
592 ms |
25056 KB |
Output is correct |
| 9 |
Correct |
584 ms |
25184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
585 ms |
25056 KB |
Output is correct |
| 2 |
Correct |
478 ms |
24672 KB |
Output is correct |
| 3 |
Correct |
470 ms |
24800 KB |
Output is correct |
| 4 |
Correct |
485 ms |
24928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 5 |
Correct |
8 ms |
5100 KB |
Output is correct |
| 6 |
Correct |
48 ms |
6124 KB |
Output is correct |
| 7 |
Correct |
539 ms |
15968 KB |
Output is correct |
| 8 |
Correct |
588 ms |
25184 KB |
Output is correct |
| 9 |
Correct |
422 ms |
16344 KB |
Output is correct |
| 10 |
Correct |
480 ms |
15868 KB |
Output is correct |
| 11 |
Correct |
411 ms |
20668 KB |
Output is correct |
| 12 |
Correct |
409 ms |
20576 KB |
Output is correct |
| 13 |
Correct |
480 ms |
24808 KB |
Output is correct |
