結果

問題 No.902 Query ζone
ユーザー chocoruskchocorusk
提出日時 2019-10-06 23:20:43
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 2,248 ms / 5,000 ms
コード長 5,325 bytes
コンパイル時間 2,262 ms
コンパイル使用メモリ 143,928 KB
実行使用メモリ 47,284 KB
最終ジャッジ日時 2023-08-02 00:03:41
合計ジャッジ時間 31,656 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 17 ms
4,376 KB
testcase_02 AC 21 ms
4,376 KB
testcase_03 AC 20 ms
4,380 KB
testcase_04 AC 18 ms
4,380 KB
testcase_05 AC 17 ms
4,380 KB
testcase_06 AC 1,574 ms
46,892 KB
testcase_07 AC 1,566 ms
47,284 KB
testcase_08 AC 1,565 ms
46,880 KB
testcase_09 AC 1,609 ms
47,108 KB
testcase_10 AC 1,600 ms
47,056 KB
testcase_11 AC 1,595 ms
47,112 KB
testcase_12 AC 1,607 ms
47,008 KB
testcase_13 AC 2,197 ms
47,020 KB
testcase_14 AC 2,222 ms
46,672 KB
testcase_15 AC 2,230 ms
46,636 KB
testcase_16 AC 2,190 ms
46,828 KB
testcase_17 AC 2,198 ms
46,808 KB
testcase_18 AC 2,248 ms
46,756 KB
testcase_19 AC 2,237 ms
46,816 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){
		auto *p=lca(u, v);
		if(p==u) return true;
		else if(p==v) return false;
		expose(p);
		int d=p->sum.first;
		expose(u);
		int du=u->sum.first;
		expose(v);
		int dv=v->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;
	cin>>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++){
		cin>>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]));
	}
	int ide=n-1;
	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;
	cin>>Q;
	for(int i=0; i<Q; i++){
		int t;
		cin>>t;
		if(t==1){
			int ui, vi, wi; ll xi;
			cin>>ui>>vi>>wi>>xi;
			int e;
			if(ui>vi) e=mp[{vi, ui}];
			else e=mp[{ui, vi}];
			lct.evert(nodev[vi]);
			lct.cut(nodev[ui]);
			lct.cut(nodee[e]);
			nodee.push_back(lct.make_node(n+ide, P(1, xi)));
			lct.link(nodee[ide], nodev[vi]);
			lct.evert(nodev[wi]);
			lct.link(nodev[wi], nodee[ide]);
			if(vi>wi) swap(vi, wi);
			mp[{vi, wi}]=ide;
			ide++;
		}else{
			int k;
			cin>>k;
			vector<int> vx(k);
			for(int j=0; j<k; j++){
				cin>>vx[j];
			}
			lct.evert(nodev[0]);
			sort(vx.begin(), vx.end(), [&](int x, int y){ return lct.comp(nodev[x], nodev[y]);});
			ll ans=0;
			for(int j=0; j<k; j++){
				int x=vx[j], y;
				if(j==k-1) y=vx[0];
				else y=vx[j+1];
				lct.evert(nodev[x]);
				lct.expose(nodev[y]);
				ans+=nodev[y]->sum.second;
			}
			ans/=2;
			cout<<ans<<endl;
		}
	}
	return 0;
}
0