結果

問題 No.901 K-ary εxtrεεmε
ユーザー QCFiumQCFium
提出日時 2020-02-12 22:20:29
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 1,505 ms / 3,000 ms
コード長 4,148 bytes
コンパイル時間 2,009 ms
コンパイル使用メモリ 180,160 KB
実行使用メモリ 25,880 KB
最終ジャッジ日時 2024-04-14 23:04:38
合計ジャッジ時間 21,637 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 847 ms
25,880 KB
testcase_01 AC 2 ms
6,812 KB
testcase_02 AC 20 ms
6,940 KB
testcase_03 AC 21 ms
6,944 KB
testcase_04 AC 22 ms
6,940 KB
testcase_05 AC 22 ms
6,940 KB
testcase_06 AC 22 ms
6,940 KB
testcase_07 AC 461 ms
24,624 KB
testcase_08 AC 468 ms
24,420 KB
testcase_09 AC 459 ms
24,628 KB
testcase_10 AC 473 ms
25,080 KB
testcase_11 AC 473 ms
23,924 KB
testcase_12 AC 784 ms
24,128 KB
testcase_13 AC 794 ms
24,528 KB
testcase_14 AC 785 ms
24,496 KB
testcase_15 AC 784 ms
25,364 KB
testcase_16 AC 782 ms
24,140 KB
testcase_17 AC 319 ms
25,632 KB
testcase_18 AC 321 ms
24,996 KB
testcase_19 AC 314 ms
24,420 KB
testcase_20 AC 318 ms
23,980 KB
testcase_21 AC 309 ms
25,368 KB
testcase_22 AC 1,497 ms
24,232 KB
testcase_23 AC 1,488 ms
24,444 KB
testcase_24 AC 1,505 ms
23,976 KB
testcase_25 AC 1,490 ms
25,512 KB
testcase_26 AC 1,470 ms
24,772 KB
testcase_27 AC 283 ms
24,712 KB
testcase_28 AC 282 ms
24,744 KB
testcase_29 AC 294 ms
24,504 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 left
#undef right
	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]);
		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