結果
| 問題 |
No.1197 モンスターショー
|
| コンテスト | |
| ユーザー |
 hos.lyric
|
| 提出日時 | 2020-08-22 15:19:21 |
| 言語 | D (dmd 2.109.1) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,266 bytes |
| コンパイル時間 | 1,829 ms |
| コンパイル使用メモリ | 158,452 KB |
| 実行使用メモリ | 19,584 KB |
| 最終ジャッジ日時 | 2024-06-22 08:16:55 |
| 合計ジャッジ時間 | 13,098 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 7 WA * 34 |
ソースコード
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
import core.bitop;
class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }
bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }
int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }
// Link-Cut Tree
// Modify val and update to the data needed
class Tree {
Tree l, r, p;
int size;
int id;
// int[] val;
long here, num, sum;
this(int id) {
l = r = p = null;
size = 1;
this.id = id;
// val = [id];
num = here;
sum = 0;
}
void update() {
size = (l ? l.size : 0) + 1 + (r ? r.size : 0);
// val = (l ? l.val : []) ~ [id] ~ (r ? r.val : []);
}
// ?
void changeP(Tree u) {
debug {
writefln("%s.changeP %s -> %s", id, p ? p.id.to!string : "null", u ? u.id.to!string : "null");
}
if (p) {
p.num -= num;
p.sum -= (num + sum);
}
p = u;
if (u) {
u.num += num;
u.sum += (num + sum);
}
}
bool isRoot() const {
return (!p || (p.l != this && p.r != this));
}
void rotate() {
// if (p.l == this) { if (r) { r.p = p; } p.l = r; r = p; }
if (p.l == this) { if (r) { r.changeP(p); } p.l = r; r = p; }
// else if (p.r == this) { if (l) { l.p = p; } p.r = l; l = p; }
else if (p.r == this) { if (l) { l.changeP(p); } p.r = l; l = p; }
Tree pp = p.p;
if (pp) {
if (pp.l == p) pp.l = this;
else if (pp.r == p) pp.r = this;
}
// p.update(); p.p = this; p = pp;
auto q = p;
p.update(); changeP(pp); q.changeP(this);
}
void splay() {
for (; !isRoot(); rotate()) {
if (!p.isRoot()) ((p.l == this) == (p.p.l == p)) ? p.rotate() : rotate();
}
update();
}
// Make the path from v to the root solid
// Return the node where it entered the last solid path
Tree expose() {
Tree u = this, v = null;
for (; u; u = u.p) { u.splay(); u.r = v; u.update(); v = u; }
splay();
return v;
}
// parent of this := u
void link(Tree u) {
// expose(); u.expose(); p = u; u.r = this; u.update();
expose(); u.expose(); changeP(u); u.r = this; u.update();
}
// parent of this := null
void cut() {
// expose(); l.p = null; l = null; update();
expose(); l.changeP(null); l = null; update();
}
// the root of the tree this belongs
Tree root() {
expose();
for (Tree u = this; ; u = u.l) if (!u.l) { u.splay(); return u; }
}
// LCA of this and u
// Assume this.root == u.root
Tree lca(Tree u) {
expose(); return u.expose();
}
// ([child of LCA, ..., this], [LCA, ..., u])
// Assume this.root == u.root
/*
import std.typecons : Tuple, tuple;
Tuple!(int[], int[]) path(Tree u) {
expose(); Tree v = u.expose(); splay(); v.splay();
auto pathT = (v == this) ? [] : ((l ? l.val : []) ~ [this.id]);
auto pathU = [v.id] ~ (v.r ? v.r.val : []);
return tuple(pathT, pathU);
}
*/
}
void print(in Tree[] nodes) {
import std.stdio : write, writeln;
import std.string : format;
string dfs(in Tree u) {
// return format("<%s%s(%s, %s)%s>",
return format("<%s%s(%s, %s, %s,%s)%s>",
u.l ? (dfs(u.l) ~ " ") : "",
// u.id, u.size, u.val,
u.id, u.size, u.here, u.num, u.sum,
u.r ? (" " ~ dfs(u.r)) : "");
}
foreach (u; nodes) {
if (u.isRoot()) {
write("| ");
if (u.p) write(u.p.id, " ");
write("<- ", u.id, ": ");
writeln(dfs(u));
}
}
}
void main() {
try {
for (; ; ) {
const N = readInt();
const K = readInt();
const Q = readInt();
auto C = new int[K];
foreach (k; 0 .. K) {
C[k] = readInt() - 1;
}
auto A = new int[N - 1];
auto B = new int[N - 1];
foreach (i; 0 .. N - 1) {
A[i] = readInt() - 1;
B[i] = readInt() - 1;
}
auto typ = new int[Q];
auto P = new int[Q];
auto D = new int[Q];
auto E = new int[Q];
foreach (q; 0 .. Q) {
typ[q] = readInt();
switch (typ[q]) {
case 1: {
P[q] = readInt() - 1;
D[q] = readInt() - 1;
} break;
case 2: {
E[q] = readInt() - 1;
} break;
default: assert(false);
}
}
auto nodes = new Tree[N];
foreach (u; 0 .. N) {
nodes[u] = new Tree(u);
}
foreach (k; 0 .. K) {
nodes[C[k]].here += 1;
nodes[C[k]].num += 1;
}
debug {
nodes.print;
writeln("----");
}
foreach (i; 0 .. N - 1) {
nodes[A[i]].link(nodes[B[i]]);
debug {
nodes.print;
writeln("----");
}
}
auto cs = C.dup;
foreach (q; 0 .. Q) {
switch (typ[q]) {
case 1: {
const k = P[q];
nodes[cs[k]].expose;
nodes[cs[k]].here -= 1;
nodes[cs[k]].num -= 1;
cs[k] = D[q];
nodes[cs[k]].expose;
nodes[cs[k]].here += 1;
nodes[cs[k]].num += 1;
} break;
case 2: {
nodes[E[q]].expose;
writeln(nodes[E[q]].sum);
} break;
default: assert(false);
}
debug {
nodes.print;
writeln("----");
}
}
}
} catch (EOFException e) {
}
}