結果

問題 No.901 K-ary εxtrεεmε
ユーザー chocoruskchocorusk
提出日時 2019-10-07 01:22:10
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,226 ms / 3,000 ms
コード長 5,445 bytes
コンパイル時間 1,772 ms
コンパイル使用メモリ 140,996 KB
実行使用メモリ 63,616 KB
最終ジャッジ日時 2024-10-11 22:45:59
合計ジャッジ時間 32,081 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,750 ms
63,616 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 24 ms
5,248 KB
testcase_03 AC 26 ms
5,248 KB
testcase_04 AC 25 ms
5,248 KB
testcase_05 AC 27 ms
5,248 KB
testcase_06 AC 27 ms
5,248 KB
testcase_07 AC 672 ms
35,968 KB
testcase_08 AC 673 ms
35,840 KB
testcase_09 AC 651 ms
35,968 KB
testcase_10 AC 668 ms
35,840 KB
testcase_11 AC 671 ms
35,840 KB
testcase_12 AC 1,055 ms
35,840 KB
testcase_13 AC 1,059 ms
35,968 KB
testcase_14 AC 1,060 ms
35,840 KB
testcase_15 AC 1,065 ms
35,840 KB
testcase_16 AC 1,054 ms
35,968 KB
testcase_17 AC 490 ms
35,840 KB
testcase_18 AC 495 ms
35,840 KB
testcase_19 AC 495 ms
35,840 KB
testcase_20 AC 493 ms
35,968 KB
testcase_21 AC 491 ms
35,840 KB
testcase_22 AC 2,165 ms
35,968 KB
testcase_23 AC 2,161 ms
35,968 KB
testcase_24 AC 2,226 ms
36,096 KB
testcase_25 AC 2,134 ms
35,944 KB
testcase_26 AC 2,163 ms
36,016 KB
testcase_27 AC 461 ms
35,860 KB
testcase_28 AC 473 ms
35,820 KB
testcase_29 AC 473 ms
35,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, ll> P;
template<typename Monoid=int>
struct LinkCutTree{
	using F=function<Monoid(Monoid, Monoid)>;
	using S=function<Monoid(Monoid)>;

	struct Node{
		Node *l, *r, *p;
		int idx;
		Monoid key, sum;

		bool rev;
		int sz;

		bool is_root(){
			return !p || (p->l!=this && p->r!=this);
		}

		Node(int idx, const Monoid &key):idx(idx), key(key), sum(key), sz(1), l(nullptr), r(nullptr), p(nullptr), rev(false) {}
	};

	const Monoid M1;
	const F f;
	const S s;

	LinkCutTree():LinkCutTree([](Monoid a, Monoid b){ return a+b;}, [](Monoid a){ return a;}, Monoid()){}
	LinkCutTree(const F &f, const S &s, const Monoid &M1):f(f), s(s), M1(M1){}

	Node *make_node(int idx, const Monoid &v=Monoid()){
		return new Node(idx, v);
	}

	void toggle(Node *t){
		assert(t);
		swap(t->l, t->r);
		t->sum=s(t->sum);
		t->rev^=true;
	}

	void push(Node *t){
		if(t->rev){
			if(t->l) toggle(t->l);
			if(t->r) toggle(t->r);
			t->rev=false;
		}
	}

	void update(Node *t){
		t->sz=1;
		t->sum=t->key;
		if(t->l) t->sz+=t->l->sz, t->sum=f(t->l->sum, t->sum);
		if(t->r) t->sz+=t->r->sz, t->sum=f(t->sum, t->r->sum);
	}

	void rotr(Node *t){
		auto *x=t->p, *y=x->p;
		if((x->l=t->r)) t->r->p=x;
		t->r=x, x->p=t;
		update(x), update(t);
		if((t->p=y)){
			if(y->l==x) y->l=t;
			if(y->r==x) y->r=t;
			update(y);
		}
	}

	void rotl(Node *t){
		auto *x=t->p, *y=x->p;
		if((x->r=t->l)) t->l->p=x;
		t->l=x, x->p=t;
		update(x), update(t);
		if((t->p=y)){
			if(y->l==x) y->l=t;
			if(y->r==x) y->r=t;
			update(y);
		}
	}

	void splay(Node* t){
		push(t);
		while(!t->is_root()){
			auto *q=t->p;
			if(q->is_root()){
				push(q), push(t);
				if(q->l==t) rotr(t);
				else rotl(t);
			}else{
				auto *r=q->p;
				push(r), push(q), push(t);
				if(r->l==q){
					if(q->l==t) rotr(q), rotr(t);
					else rotl(t), rotr(t);
				}else{
					if(q->r==t) rotl(q), rotl(t);
					else rotr(t), rotl(t);
				}
			}
		}
	}

	Node *expose(Node *t){
		Node *rp=nullptr;
		for(Node *cur=t; cur; cur=cur->p){
			splay(cur);
			cur->r=rp;
			update(cur);
			rp=cur;
		}
		splay(t);
		return rp;
	}

	void link(Node *child, Node *parent){
		expose(child);
		expose(parent);
		child->p=parent;
		parent->r=child;
		update(parent);
	}

	void cut(Node *child){
		expose(child);
		auto *parent=child->l;
		child->l=nullptr;
		parent->p=nullptr;
		update(child);
	}

	void evert(Node *t){
		expose(t);
		toggle(t);
		push(t);
	}

	Node *lca(Node *u, Node *v){
		//if(get_root(u)!=get_root(v)) return nullptr;
		expose(u);
		return expose(v);
	}

	Node *get_root(Node *x){
		expose(x);
		while(x->l){
			push(x);
			x=x->l;
		}
		return x;
	}

	Node *get_kth(Node *v, int k){
		expose(v);
		while(v){
			push(v);
			if(v->r && v->r->sz>k){
				v=v->r;
			}else{
				if(v->r) k-=v->r->sz;
				if(k==0) return v;
				k--;
				v=v->l;
			}
		}
		return nullptr;
	}

	bool comp(Node *u, Node *v, int du, int dv){
		auto *p=lca(u, v);
		if(p==u) return true;
		else if(p==v) return false;
		expose(p);
		int d=p->sum.first;
		return get_kth(u, 2*(du-d-1))->idx < get_kth(v, 2*(dv-d-1))->idx;
	}
};
int a[100010], b[100010]; ll w[100010];
int main()
{
	int n;
	scanf("%d", &n);
	using LCT=LinkCutTree<P>;
	auto f=[](P a, P b){ return P(a.first+b.first, a.second+b.second);};
	LCT lct(f, [](P a){ return a;}, P(0, 0));
	vector<LCT::Node*> nodev(n), nodee(n-1);
	for(int i=0; i<n; i++){
		nodev[i]=lct.make_node(i, P(0, 0));
	}
	vector<vector<P>> g(n);
	map<P, int> mp;
	for(int i=0; i<n-1; i++){
		scanf("%d %d %lld", &a[i], &b[i], &w[i]);
		if(a[i]>b[i]) swap(a[i], b[i]);
		mp[{a[i], b[i]}]=i;
		g[a[i]].push_back({b[i], i});
		g[b[i]].push_back({a[i], i});
		nodee[i]=lct.make_node(n+i, P(1, w[i]));
	}
	auto dfs=[&](auto dfs, int u, int p)->void{
		for(auto q:g[u]){
			if(q.first==p) continue;
			lct.link(nodee[q.second], nodev[u]);
			lct.link(nodev[q.first], nodee[q.second]);
			dfs(dfs, q.first, u);
		}
	};
	dfs(dfs, 0, -1);
	int Q;
	scanf("%d", &Q);
	for(int i=0; i<Q; i++){
		int t=2;
		//scanf("%d", &t);
		if(t==1){
			int ui, vi, wi; ll xi;
			scanf("%d %d %d %lld", &ui, &vi, &wi, &xi);
			int e;
			if(ui>vi){
				e=mp[{vi, ui}];
				mp.erase({vi, ui});
			}else{
				e=mp[{ui, vi}];
				mp.erase({ui, vi});
			}
			lct.evert(nodev[vi]);
			lct.cut(nodev[ui]);
			nodee[e]->key=P(1, xi);
			lct.evert(nodev[wi]);
			lct.link(nodev[wi], nodee[e]);
			if(vi>wi) swap(vi, wi);
			mp[{vi, wi}]=e;
		}else{
			int k;
			scanf("%d", &k);
			vector<int> vx(k), ind(k);
			vector<int> vd(k);
			for(int j=0; j<k; j++){
				scanf("%d", &vx[j]);
				ind[j]=j;
				lct.expose(nodev[vx[j]]);
				vd[j]=nodev[vx[j]]->sum.first;
			}
			sort(ind.begin(), ind.end(), [&](int x, int y){ return lct.comp(nodev[vx[x]], nodev[vx[y]], vd[x], vd[y]);});
			ll ans=0;
			for(int j=0; j<k; j++){
				int x=vx[ind[j]], y;
				if(j==k-1) y=vx[ind[0]];
				else y=vx[ind[j+1]];
				lct.evert(nodev[x]);
				lct.expose(nodev[y]);
				ans+=nodev[y]->sum.second;
			}
			ans/=2;
			printf("%lld\n", ans);
		}
	}
	return 0;
}
0