結果

問題 No.902 Query ζone
ユーザー QCFiumQCFium
提出日時 2020-02-13 16:13:32
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 928 ms / 5,000 ms
コード長 4,512 bytes
コンパイル時間 1,800 ms
コンパイル使用メモリ 186,044 KB
実行使用メモリ 25,772 KB
最終ジャッジ日時 2024-10-06 03:25:08
合計ジャッジ時間 14,581 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 9 ms
6,820 KB
testcase_02 AC 11 ms
6,816 KB
testcase_03 AC 11 ms
6,816 KB
testcase_04 AC 10 ms
6,816 KB
testcase_05 AC 9 ms
6,820 KB
testcase_06 AC 557 ms
24,028 KB
testcase_07 AC 578 ms
24,208 KB
testcase_08 AC 573 ms
25,380 KB
testcase_09 AC 577 ms
24,868 KB
testcase_10 AC 568 ms
25,096 KB
testcase_11 AC 562 ms
24,864 KB
testcase_12 AC 564 ms
24,596 KB
testcase_13 AC 910 ms
25,480 KB
testcase_14 AC 878 ms
24,596 KB
testcase_15 AC 882 ms
25,072 KB
testcase_16 AC 889 ms
24,332 KB
testcase_17 AC 919 ms
25,772 KB
testcase_18 AC 886 ms
24,316 KB
testcase_19 AC 928 ms
24,168 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

struct LCT {
#define l ch[0]
#define r ch[1]
	struct Node {
		Node *p;
		Node *ch[2];
		int len_sum;
		int64_t sum;
		int len;
		int val;
		int size;
		int index;
		bool rev;
		void flush() {
			if (rev) {
				l->rev ^= 1;
				r->rev ^= 1;
				std::swap(l, r);
				rev = false;
			}
		}
		void fetch() {
			len_sum = len + l->len_sum + r->len_sum;
			sum = val + l->sum + r->sum;
			size = 1 + l->size + r->size;
		}
		void rotate(int dir) {
			Node *new_root = ch[!dir];
			ch[!dir] = new_root->ch[dir];
			ch[!dir]->p = this;
			new_root->ch[dir] = this;
			if (p->l == this) p->l = new_root;
			else if (p->r == this) p->r = new_root;
			new_root->p = p;
			p = new_root;
			fetch();
			new_root->fetch();
		}
		bool is_root() { return p == LCT::NONE || (p->l != this && p->r != this); }
		void splay() {
			flush();
			while (!is_root()) {
				if (p->is_root()) {
					p->flush(), flush();
					p->rotate(p->l == this);
				} else {
					Node *pp = p->p;
					pp->flush(), p->flush(), flush();
					bool flag1 = pp->l == p;
					bool flag2 = p->l == this;
					if (flag1 == flag2) pp->rotate(flag1);
					p->rotate(flag2);
					if (flag1 != flag2) pp->rotate(flag1);
				}
			}
		}
	};
	Node *expose(Node *start) {
		Node *prev = NONE;
		for (Node *cur = start; cur != NONE; cur = cur->p) {
			cur->splay();
			cur->r = prev;
			cur->fetch();
			prev = cur;
		}
		start->splay();
		return prev;
	}
	void link(Node *child, Node *parent) {
		expose(child);
		expose(parent);
		child->p = parent;
		parent->r = child;
		parent->fetch();
	}
	void cut(Node *child) {
		expose(child);
		Node *parent = child->l;
		parent->p = NONE;
		child->l = NONE;
		child->fetch();
	}
	void evert(Node *root) {
		expose(root);
		root->rev ^= 1;
		root->flush();
	}
	Node *root(Node *node) {
		expose(node);
		for (; node->flush(), (node->l != NONE); node = node->l);
		node->splay();
		return node;
	}
	Node *lca(Node *a, Node *b) {
		if (root(a) != root(b)) return NONE;
		expose(a);
		return expose(b);
	}
	Node *climb(Node *node, int dist) {
		expose(node);
		while (dist) {
			if (dist > 0) (node = node->l)->flush(), dist -= node->r->size + 1;
			else (node = node->r)->flush(), dist += node->l->size + 1;
		}
		node->splay();
		return node;
	}
#undef l
#undef r
	static Node *nodes, *NONE;
	static int head;
	LCT () {
		if (!head) nodes[head++] = {NONE, {NONE, NONE}, 0, 0, 0, 0, 0, -1, false};
	}
	Node *new_node(int len, int val, int index) {
		return &(nodes[head++] = {NONE, {NONE, NONE}, len, val, len, val, 1, index, false});
	}
};
LCT::Node *LCT::nodes = (Node *) malloc(sizeof(Node) * 1000000), *LCT::NONE = nodes;
int LCT::head = 0;

int main() {
	int n = ri();
	std::map<std::pair<int, int>, int> hens;
	for (int i = 0; i + 1 < n; i++) {
		int a = ri();
		int b = ri();
		int c = ri();
		if (a > b) std::swap(a, b);
		hens[{a, b}] = c;
	}
	
	using Node = LCT::Node;
	LCT tree;
	Node *nodes[2 * n - 1];
	for (int i = 0; i < n; i++) nodes[i] = tree.new_node(0, 0, i);
	int cnt = n;
	for (auto i : hens) {
		tree.evert(nodes[i.first.first]);
		tree.evert(nodes[i.first.second]);
		nodes[cnt] = tree.new_node(1, i.second, -1);
		tree.link(nodes[i.first.first], nodes[cnt]);
		tree.link(nodes[i.first.second], nodes[cnt]);
		cnt++;
	}
	
	auto comp = [&] (int i, int j) {
		Node *lca = tree.lca(nodes[i], nodes[j]);
		if (lca == nodes[i]) return false;
		if (lca == nodes[j]) return true;
		tree.evert(lca);
		tree.expose(nodes[i]);
		int i_dist = nodes[i]->len_sum;
		tree.expose(nodes[j]);
		int j_dist = nodes[j]->len_sum;
		tree.evert(nodes[0]);
		i = tree.climb(nodes[i], (i_dist - 1) * 2)->index;
		j = tree.climb(nodes[j], (j_dist - 1) * 2)->index;
		return i < j;
	};
	
	int q = ri();
	for (int i = 0; i < q; i++) {
		tree.evert(nodes[0]);
		if (ri() == 1) {
			int r0 = ri();
			int r1 = ri();
			int r2 = ri();
			int val = ri();
			tree.evert(nodes[r0]);
			Node *hen = tree.climb(nodes[r1], 1);
			tree.expose(nodes[r1]);
			tree.cut(hen);
			tree.cut(nodes[r1]);
			hen->val = hen->sum = val;
			tree.evert(nodes[r2]);
			tree.link(nodes[r2], hen);
			tree.link(hen, nodes[r1]);
		} else {
			int k = ri();
			int b[k];
			for (auto &j : b) j = ri();
			std::sort(b, b + k, comp);
			int64_t res = 0;
			for (int j = 0; j < k; j++) {
				int next = (j + 1) % k;
				tree.evert(nodes[b[j]]);
				tree.expose(nodes[b[next]]);
				res += nodes[b[next]]->sum;
			}
			printf("%lld\n", (long long) (res / 2));
		}
	}
	
	return 0;
}
0