#pragma GCC target ("avx") #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 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using ld = long double; #define int long long #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 H pair #define P pair> #define Q(i,j,k) mkp(i,mkp(j,k)) #define rng(i,s,n) for(int i = (s) ; i < (n) ; i++) #define rep(i,n) rng(i, 0, (n)) #define mkp make_pair #define vec vector #define vi vec #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,i) (lower_bound(all(b),(i))-(b).begin()) #define ssp(i,n) (i==(int)(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) int quetimes_=(n);rep(qq123_,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.find(x)!=a.end()) //#define endl "\n" constexpr int mod = (ll)1e9 + 7; constexpr int 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 }; templatebool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } templatebool 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 popcount(ll x) { int sum = 0; for (int i = 0; i < 60; i++)if ((1ll << i) & x) sum++; return sum; } template class csum { vec v; public: csum(vec& a) :v(a) { build(); } csum(){} void init(vec& a) { v = a; build(); } void build() { for (int i = 1; i < v.size(); i++) v[i] += v[i - 1]; } 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); }//[l,r) T a(pairt) { return a(t.first, t.second); } T b(pairt) { return b(t.first, t.second); } }; class mint { public:ll v; mint(ll v = 0) { s(v % mod + mod); } constexpr static int mod = (ll)1e9 + 7; constexpr static int fn_ = (ll)2e6 + 5; static mint fact[fn_], comp[fn_]; mint pow(int x) const { mint b(v), c(1); while (x) { if (x & 1) c *= b; b *= b; x >>= 1; } return c; } inline mint& s(int vv) { v = vv < mod ? vv : vv - mod; return *this; } inline mint inv()const { return pow(mod - 2); } inline mint operator-()const { return mint() - *this; } inline mint& operator+=(const mint b) { return s(v + b.v); } inline mint& operator-=(const mint b) { return s(v + mod - b.v); } inline mint& operator*=(const mint b) { v = v * b.v % mod; return *this; } inline mint& operator/=(const mint b) { v = v * b.inv().v % mod; return *this; } inline mint operator+(const mint b) const { return mint(v) += b; } inline mint operator-(const mint b) const { return mint(v) -= b; } inline mint operator*(const mint b) const { return mint(v) *= b; } inline mint operator/(const mint b) const { return mint(v) /= b; } friend ostream& operator<<(ostream& os, const mint& m) { return os << m.v; } friend istream& operator>>(istream& is, mint& m) { int x; is >> x; m = mint(x); return is; } bool operator<(const mint& r)const { return v < r.v; } bool operator>(const mint& r)const { return v > r.v; } bool operator<=(const mint& r)const { return v <= r.v; } bool operator>=(const mint& r)const { return v >= r.v; } bool operator==(const mint& r)const { return v == r.v; } bool operator!=(const mint& r)const { return v != r.v; } explicit operator bool()const { return v; } explicit operator int()const { return v; } mint comb(mint k) { if (k > * this) return mint(); if (!fact[0]) combinit(); if (v >= fn_) { if (k > * this - k) k = *this - k; mint tmp(1); for (int i = v; i >= v - k.v + 1; i--) tmp *= mint(i); return tmp * comp[k.v]; } return fact[v] * comp[k.v] * comp[v - k.v]; }//nCk mint perm(mint k) { if (k > * this) return mint(); if (!fact[0]) combinit(); if (v >= fn_) { mint tmp(1); for (int i = v; i >= v - k.v + 1; i--) tmp *= mint(i); return tmp; } return fact[v] * comp[v - k.v]; }//nPk static void combinit() { fact[0] = 1; for (int i = 1; i < fn_; i++) fact[i] = fact[i - 1] * mint(i); comp[fn_ - 1] = fact[fn_ - 1].inv(); for (int i = fn_ - 2; i >= 0; i--) comp[i] = comp[i + 1] * mint(i + 1); } }; mint mint::fact[fn_], mint::comp[fn_]; //-------------------------------------------------------------- auto RUQ = [](int& num, int x, int width) {num = x; }; auto RAQ = [](int& num, int x, int width) {num += x; }; auto RCMXQ = [](int& num, int x, int width) {num = max(num, x); }; auto RCMNQ = [](int& num, int x, int width) {num = min(num, x); }; auto RASQ = [](int& num, int x, int width) {num += (x * width); }; auto RUSQ = [](int& num, int x, int width) {num = (x * width); }; auto RSQ = [](int x, int y)->int {return x + y; }; auto RMXQ = [](int x, int y)->int {return max(x, y); }; auto RMNQ = [](int x, int y)->int {return min(x, y); }; class Segtree { #define SEG_SIZE 900000 using F = function; using T = function; int siz, rr, zer, zer2; int dat[SEG_SIZE], lazy[SEG_SIZE]; bool updated[SEG_SIZE]; F upd; T qur; public: //for update, for query void init(int size, F update, T query, int zero, int zero2) { siz = size, upd = update, qur = query, zer = zero2, zer2 = zero; rr = 1; while (rr < size) rr *= 2; for (int i = 0; i < SEG_SIZE; i++) dat[i] = zer, lazy[i] = zer2, updated[i] = 0; } void rmnq(int n) { init(n, RUQ, RMNQ, 0, inf); } void rmxq(int n) { init(n, RUQ, RMXQ, 0, -inf); } template void build(const Iterator st, const Iterator ed) { Iterator it = st; int cur = rr - 1; while (it != ed) dat[cur++] = (*it++); for (int i = rr - 2; i >= 0; i--) dat[i] = qur(dat[i * 2 + 1], dat[i * 2 + 2]); } void build(vectorv) { for (int i = 0; i < min((int)v.size(), siz); i++) dat[i + rr - 1] = v[i]; for (int i = rr - 2; i >= 0; i--) dat[i] = qur(dat[i * 2 + 1], dat[i * 2 + 2]); } void update(int a, int b, int x) { update(0, a, b, 0, rr, x); } void change(int a, int x) { change2(a, x); }//一点更新 int query(int a, int b) { return query(0, a, b, 0, rr); } int lower_bound(int a, int b, functioncomp) { return lower_bound(0, a, b, 0, rr, comp); } int upper_bound(int a, int b, functioncomp) { return upper_bound(0, a, b, 0, rr, comp); } int operator[](const int i) { return query(i, i + 1); } private: void eval(int i, int l, int r) { if (!updated[i]) return; if (r - l > 1) { upd(lazy[i * 2 + 1], lazy[i], 1); upd(lazy[i * 2 + 2], lazy[i], 1); updated[i * 2 + 1] = updated[i * 2 + 2] = 1; } upd(dat[i], lazy[i], min(r, siz) - l); lazy[i] = zer2; updated[i] = 0; } void update(int i, int a, int b, int l, int r, int x) { eval(i, l, r); if (b <= l || r <= a) return; if (a <= l && r <= b) { upd(lazy[i], x, 1); updated[i] = 1; eval(i, l, r); return; } update(i * 2 + 1, a, b, l, (l + r) / 2, x); update(i * 2 + 2, a, b, (l + r) / 2, r, x); dat[i] = qur(dat[i * 2 + 1], dat[i * 2 + 2]); } void change2(int a, int x) { query(a, a + 1); int t = a + rr - 1; dat[t] = x; while (t > 0) { t = (t - 1) / 2; dat[t] = qur(dat[t * 2 + 1], dat[t * 2 + 2]); } } int query(int i, int a, int b, int l, int r) { eval(i, l, r); if (b <= l || r <= a) return zer; if (a <= l && r <= b) return dat[i]; return qur(query(i * 2 + 1, a, b, l, (l + r) / 2), query(i * 2 + 2, a, b, (l + r) / 2, r)); } int lower_bound(int i, int a, int b, int l, int r, functioncomp) { eval(i, l, r); if (b <= l || r <= a || !comp(dat[i])) return siz; if (r - l == 1) return l; int tmp = lower_bound(i * 2 + 1, a, b, l, (l + r) / 2, comp); if (tmp < siz) return tmp; return lower_bound(i * 2 + 2, a, b, (l + r) / 2, r, comp); } int upper_bound(int i, int a, int b, int l, int r, functioncomp) { eval(i, l, r); if (b <= l || r <= a || !comp(dat[i])) return 0; if (r - l == 1) return r; int tmp = upper_bound(i * 2 + 2, a, b, (l + r) / 2, r, comp); if (tmp > 0) return tmp; return upper_bound(i * 2 + 1, a, b, l, (l + r) / 2, comp); } }; class HLD { #define HLD_SIZ 400010 #define H pair #define pb emplace_back #define fs first #define sc second using F = function; using T = function; int n, st, zer, zer2, idx; bool mde; int siz[HLD_SIZ]; vectore[HLD_SIZ]; vector>>f; int in[HLD_SIZ], out[HLD_SIZ], rev[HLD_SIZ]; int head[HLD_SIZ], prt[HLD_SIZ], dept[HLD_SIZ]; Segtree seg; F upd; T qur; public: //for update, for query, mode(0:vertex, 1:edge) void init(int size, F update, T query, int zero, int zero2, bool mode) { n = size, zero = zer, zer2 = zero2; upd = update, qur = query; mde = mode; f.clear(); for (int i = 0; i <= n; i++) { siz[i] = 0, prt[i] = -1, head[i] = -1; in[i] = 0, out[i] = 0, rev[i] = 0; dept[i] = 0; e[i].clear(); } } void add_edge(int u, int v, int r) { add_edge(u, v); f.pb(make_pair(u, make_pair(v, r))); } void add_edge(int u, int v) { e[u].pb(v); e[v].pb(u); } void build(int root = 0) { st = root; dept[st] = 0; for (auto u : e[st]) normalize(u, st, 1); for (int i = 0; i <= n; i++) if (i != st && !(~prt[i])) { dept[i] = 0; for (auto u : e[i]) normalize(u, i, 1); } for (int i = 0; i <= n; i++) if (!(~prt[i])) dfs1(i); for (int i = 0; i <= n; i++) if (!(~prt[i])) { head[i] = i; dfs2(i); } seg.init(idx, upd, qur, zer, zer2); if (f.size()) { vectorv(idx, zer2); for (auto g : f) { v[max(in[g.fs], in[g.sc.fs])] = g.sc.sc; } seg.build(v); } } void update(int a, int b, int x) { while (head[a] != head[b]) { if (in[a] > in[b]) swap(a, b); seg.update(in[head[b]], in[b] + 1, x); b = prt[head[b]]; } if (in[a] > in[b]) swap(a, b); seg.update(in[a] + mde, in[b] + 1, x); } int query(int a, int b) { int ret = zer2; while (head[a] != head[b]) { if (in[a] > in[b]) swap(a, b); ret = qur(ret, seg.query(in[head[b]], in[b] + 1)); b = prt[head[b]]; } if (in[a] > in[b]) swap(a, b); ret = qur(ret, seg.query(in[a] + mde, in[b] + 1)); return ret; } int lca(int a, int b) { while (1) { if (in[a] > in[b]) swap(a, b); if (head[a] == head[b]) return a; b = prt[head[b]]; } } void subupdate(int a, int x) { seg.update(in[a], out[a], x); } int subquery(int a) { return seg.query(in[a], out[a]); } int par(int x, int t) { while (1) { if (in[x] - in[head[x]] >= t) return rev[in[head[x]] + ((in[x] - in[head[x]]) - t)]; t -= (in[x] - in[head[x]] + 1); x = prt[head[x]]; } } int operator[](const int& i) { return dept[i]; } private: void normalize(int v, int p, int d) { dept[v] = d; prt[v] = p; for (auto& u : e[v]) { if (u == e[v].back()) break; if (u == p) swap(u, e[v].back()); normalize(u, v, d + 1); } if (!e[v].empty()) e[v].pop_back(); } void dfs1(int v) { siz[v] = 1; for (int& u : e[v]) { dfs1(u); siz[v] += siz[u]; if (siz[u] > siz[e[v][0]]) { swap(u, e[v][0]); } } } void dfs2(int v) { rev[idx] = v; in[v] = idx++; for (auto u : e[v]) { head[u] = (u == e[v][0] ? head[v] : u); dfs2(u); } out[v] = idx; } }; //--------------------------------------------------------------------- int n, k, q; vi a; vece; vi f[200000]; vec

queries; HLD hld, hld2; int c[200000]; mt19937 rnd(114514); void generate(int mode, int num) { a.clear(); e.clear(); queries.clear(); rep(i, 200000) { f[i].clear(); c[i] = 0; } if (mode == 0) { cin >> n >> k >> q; rep(i, k) a.pb(read()-1); rep(i, n - 1) { e.pb(readh(1)); f[e.back().fs].pb(e.back().sc); f[e.back().sc].pb(e.back().fs); } rep(i, q) { int t; cin >> t; int u, v = 1; if (t == 1) cin >> u >> v; else if (t == 2) cin >> u; u--; v--; queries.pb(Q(t, u, v)); } } else { ofstream ofs("input/" + to_string(num) + ".txt"); n = rnd() % 100000 + 1, k = rnd() % 100000 + 1, q = rnd() % 100000 + 1; if (num <= 7) { n = n % (num + 1) + 1; k = k % (num + 1) + 1; q = q % (num + 1) + 1; } else if (num <= 34) { } else if (num <= 38) { n = 99800; k = 99800; q = 99800; } else { n = 100000, k = 100000, q = 100000; } ofs << n << " " << k << " " << q << endl; rep(i, k) { int p = rnd() % n + 1; ofs << p << ssp(i, k); a.pb(p - 1); } rng(i, 1, n) { int t = rnd() % i; if (num == 8) { t = i - 1; } H g = H{ i + 1,t + 1 }; e.pb(H{ i,t }); ofs << g.fs << " " << g.sc << endl; f[i].pb(t); f[t].pb(i); } cdf(q) { int t = rnd() % 2 + 1; if (t == 1) { int p = rnd() % k; int d = rnd() % n; queries.pb(Q(t, p, d)); ofs << 1 << " " << p + 1 << " " << d + 1 << endl; } else { int d = rnd() % n; queries.pb(Q(t, d, 0)); ofs << 2 << " " << d + 1 << endl; } } } } vi guchoku() { vi b = a; vi dep(n, 0); vi par(n, 0); vi ans; function dfs = [&](int x, int p, int d) -> void{ dep[x] = d; par[x] = p; for (auto g : f[x]) { if (g != p) dfs(g, x, d + 1); } }; dfs(0, -1, 0); for (auto g : queries) { if (g.xx == 1) { b[g.yy] = g.zz; } else { int d = g.yy; auto func = [&]() ->int{ vi e(n, 0); rep(i, k) { int x = b[i], y = d; while (x != y) { if (dep[x] > dep[y]) swap(x, y); e[y]++; y = par[y]; } } int ans = 0; rep(i, n) ans += e[i]; return ans; }; ans.pb(func()); } } return ans; } vi solve() { hld.init(n, RASQ, RSQ, 0, 0, 1); hld2.init(n, RASQ, RSQ, 0, 0, 0); function dfs = [&](int x, int p, int d) { c[x] = d; for (auto g : f[x]) { if (g != p) dfs(g, x, d); } }; for (auto g : f[0]) dfs(g, 0, g); rep(i, n - 1) { hld.add_edge(e[i].fs, e[i].sc); hld2.add_edge(e[i].fs, e[i].sc); } hld.build(0); hld2.build(0); vi b = a; int ans = 0; rep(i, k) { hld.update(0, b[i], 1); hld2.update(b[i], b[i], 1); ans += hld[b[i]]; } vi ret; for (auto g : queries) { if (g.xx == 1) { ans -= hld[b[g.yy]]; hld.update(0, b[g.yy], -1); hld2.update(b[g.yy], b[g.yy], -1); b[g.yy] = g.zz; hld.update(0, b[g.yy], 1); hld2.update(b[g.yy], b[g.yy], 1); ans += hld[b[g.yy]]; } else { int t = ans; int r = hld[g.yy] * hld2.subquery(c[g.yy]); // int d = hld.query(0, g.yy); //0からゴールまでのパスで、使用されたのは何回ですか? int h = (k - hld2.subquery(c[g.yy])) * hld[g.yy]; //ゴールと全くパスを共有していない人たちは、深さ分だけコストが加算される ret.pb((t - d) + (r - d) + h); } } return ret; } signed main() { generate(0, 0); vi ans = guchoku(); for (auto g : ans) cout << g << endl; }