結果

問題 No.1197 モンスターショー
ユーザー chocoruskchocorusk
提出日時 2020-08-22 16:09:47
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 709 ms / 3,000 ms
コード長 4,618 bytes
コンパイル時間 1,722 ms
コンパイル使用メモリ 139,692 KB
実行使用メモリ 38,240 KB
最終ジャッジ日時 2024-04-23 17:55:23
合計ジャッジ時間 15,449 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 121 ms
26,832 KB
testcase_08 AC 156 ms
18,848 KB
testcase_09 AC 350 ms
31,116 KB
testcase_10 AC 542 ms
29,904 KB
testcase_11 AC 263 ms
12,648 KB
testcase_12 AC 134 ms
8,576 KB
testcase_13 AC 191 ms
21,428 KB
testcase_14 AC 385 ms
21,720 KB
testcase_15 AC 259 ms
11,852 KB
testcase_16 AC 565 ms
35,948 KB
testcase_17 AC 530 ms
36,208 KB
testcase_18 AC 206 ms
14,480 KB
testcase_19 AC 491 ms
29,896 KB
testcase_20 AC 100 ms
12,248 KB
testcase_21 AC 203 ms
6,144 KB
testcase_22 AC 27 ms
5,888 KB
testcase_23 AC 484 ms
23,276 KB
testcase_24 AC 341 ms
23,152 KB
testcase_25 AC 176 ms
16,416 KB
testcase_26 AC 303 ms
17,224 KB
testcase_27 AC 423 ms
32,864 KB
testcase_28 AC 353 ms
18,964 KB
testcase_29 AC 249 ms
22,376 KB
testcase_30 AC 222 ms
25,448 KB
testcase_31 AC 233 ms
20,348 KB
testcase_32 AC 172 ms
5,376 KB
testcase_33 AC 156 ms
16,544 KB
testcase_34 AC 693 ms
38,056 KB
testcase_35 AC 709 ms
38,056 KB
testcase_36 AC 707 ms
38,060 KB
testcase_37 AC 696 ms
38,240 KB
testcase_38 AC 690 ms
38,088 KB
testcase_39 AC 698 ms
38,088 KB
testcase_40 AC 448 ms
35,656 KB
testcase_41 AC 2 ms
5,376 KB
testcase_42 AC 2 ms
5,376 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>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
struct LinkCutTree{
	struct Node{
		Node *l, *r, *p;
		bool rev;
		int idx, val, sz, szl;
		ll cost, sum, suml, costs, sum2;
		set<pair<int, int>> dat;
		Node(int val, int idx, ll cost):cost(cost), costs(cost), sum(0), sum2(0), suml(0), idx(idx), val(val), sz(val), szl(0), rev(false), l(nullptr), r(nullptr), p(nullptr){}
		bool is_root(){
			return !p || (p->l!=this && p->r!=this);
		}
	};
	vector<Node*> v;
	LinkCutTree(int n){
		v.resize(n);
		for(int i=0; i<n; i++) v[i]=new Node(0, i, 0);
	}
	void toggle(Node *t){
		if(!t) return;
		swap(t->sum, t->sum2);
		swap(t->l, t->r);
		t->rev^=true;
	}
	void push(Node *t){
		if(!t) return;
		if(t->rev){
			toggle(t->l);
			toggle(t->r);
			t->rev=false;
		}
	}
	void update(Node *t){
		t->sz=t->val+t->szl, t->costs=t->cost;
		if(t->l) t->sz+=t->l->sz, t->costs+=t->l->costs;
		if(t->r) t->sz+=t->r->sz, t->costs+=t->r->costs;
		t->sum=t->suml+t->cost*t->szl;
		t->sum2=t->suml+t->cost*t->szl;
		if(t->l) t->sum+=t->l->sum, t->sum2+=t->l->sum2, t->sum+=t->l->costs*(t->val+t->szl), t->sum2+=t->l->sz*t->cost;
		if(t->r) t->sum+=t->r->sum, t->sum2+=t->r->sum2, t->sum+=t->r->sz*t->cost, t->sum2+=t->r->costs*(t->val+t->szl);
		if(t->l && t->r) t->sum+=t->l->costs*t->r->sz, t->sum2+=t->r->costs*t->l->sz;
	}
	void rotate(Node *t){
		Node *p=t->p, *pp=p->p, *ch;
		if(p->l==t) ch=t->r;
		else ch=t->l;
		if(pp){
			if(pp->l==p) pp->l=t;
			else if(pp->r==p) pp->r=t;
			else{
				pp->dat.erase({p->sz, p->idx});
				pp->dat.insert({p->sz, t->idx});
			}
		}
		t->p=pp;
		if(p->l==t) t->r=p;
		else t->l=p;
		p->p=t;
		if(p->l==t) p->l=ch;
		else p->r=ch;
		if(ch) ch->p=p;
		update(p);
		update(t);
	}
	int state(Node *t){
		if(t->is_root()) return 0;
		else if(t->p->l==t) return 1;
		else return -1;
	}
	void splay(Node *t){
		push(t);
		while(state(t)){
			if(!state(t->p)){
				push(t->p); push(t);
				rotate(t);
			}else{
				push(t->p->p); push(t->p); push(t);
				if(state(t->p)==state(t)){
					rotate(t->p);
					rotate(t);
				}else{
					rotate(t);
					rotate(t);
				}
			}
		}
	}
	Node *expose(Node *t){
		Node *rp=nullptr;
		for(Node *now=t; now; now=now->p){
			splay(now);
			if(rp){
				now->dat.erase({rp->sz, rp->idx});
				now->szl-=rp->sz;
				now->suml-=rp->sum;
			}
			if(now->r){
				now->dat.insert({now->r->sz, now->r->idx});
				now->szl+=now->r->sz;
				now->suml+=now->r->sum;
			}
			now->r=rp;
			update(now);
			rp=now;
		}
		splay(t);
		return rp;
	}
	void link(Node *c, Node *p){
		expose(c);
		expose(p);
		p->r=c;
		c->p=p;
		update(p);
	}
	void cut(Node *c){
		expose(c);
		c->l->p=nullptr;
		c->l=nullptr;
		update(c);
	}
	void evert(Node *t){
		expose(t);
		toggle(t);
		push(t);
	}
	Node *find(Node *t){
		evert(t);
		int n=t->sz, m=(n+1)/2;
		if(n==0) return t;
		Node *now=t;
		while(1){
			push(now);
			if(now->r && now->r->sz>=m) now=now->r;
			else if((now->r?now->r->sz:0)+now->szl+now->val<m){
				m-=(now->r?now->r->sz:0)+now->szl+now->val;
				now=now->l;
			}else{
				if(now->dat.empty() || (*now->dat.rbegin()).first<=n/2) return now;
				else{
					m=(n+1)/2;
					now=v[(*now->dat.rbegin()).second];
				}
			}
		}
	}
};
int main()
{
	int n, k, q;
	scanf("%d %d %d", &n, &k, &q);
	LinkCutTree lct(n);
	using node=LinkCutTree::Node;
    int c[100010];
    for(int i=0; i<k; i++){
        scanf("%d", &c[i]);
        c[i]--;
        lct.v[c[i]]->val++;
    }
    for(int i=0; i<n-1; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        a--; b--;
        node *e=new node(0, i+n, 1);
        lct.v.push_back(e);
		lct.link(e, lct.v[a]);
		lct.evert(e);
		lct.link(e, lct.v[b]);
    }
    while(q--){
        int t; scanf("%d", &t);
        if(t==1){
            int p, d;
            scanf("%d %d", &p, &d);
            p--; d--;
            lct.expose(lct.v[c[p]]);
            lct.v[c[p]]->val--;
            c[p]=d;
            lct.expose(lct.v[c[p]]);
            lct.v[c[p]]->val++;
        }else{
            int e; scanf("%d", &e);
            e--;
            lct.evert(lct.v[e]);
            printf("%lld\n", lct.v[e]->sum);
        }
    }
	return 0;
}
0