結果

問題 No.1197 モンスターショー
ユーザー 沙耶花沙耶花
提出日時 2020-08-22 15:36:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,524 bytes
コンパイル時間 2,500 ms
コンパイル使用メモリ 216,844 KB
実行使用メモリ 31,616 KB
最終ジャッジ日時 2024-04-23 09:56:06
合計ジャッジ時間 11,705 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
13,888 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 625 ms
31,616 KB
testcase_08 AC 299 ms
13,696 KB
testcase_09 AC 1,238 ms
21,888 KB
testcase_10 AC 2,877 ms
21,120 KB
testcase_11 AC 952 ms
9,728 KB
testcase_12 AC 362 ms
6,940 KB
testcase_13 AC 454 ms
15,232 KB
testcase_14 AC 1,681 ms
15,744 KB
testcase_15 AC 857 ms
9,088 KB
testcase_16 AC 2,905 ms
25,216 KB
testcase_17 AC 2,588 ms
25,312 KB
testcase_18 AC 689 ms
10,880 KB
testcase_19 AC 2,474 ms
21,120 KB
testcase_20 AC 227 ms
9,344 KB
testcase_21 AC 557 ms
6,944 KB
testcase_22 AC 42 ms
6,944 KB
testcase_23 AC 2,319 ms
16,896 KB
testcase_24 AC 1,412 ms
16,640 KB
testcase_25 AC 494 ms
12,160 KB
testcase_26 AC 1,143 ms
12,800 KB
testcase_27 AC 1,651 ms
23,040 KB
testcase_28 AC 1,507 ms
14,080 KB
testcase_29 AC 767 ms
16,128 KB
testcase_30 AC 478 ms
18,176 KB
testcase_31 AC 748 ms
14,592 KB
testcase_32 AC 481 ms
6,948 KB
testcase_33 AC 383 ms
12,288 KB
testcase_34 TLE -
testcase_35 TLE -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define modulo 998244353
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000005

struct lca{
	
	vector<int> depth;//depth[i] 頂点iの深さ
	vector<vector<int>> parents;//parents[i][j] 頂点iから2^j個上の親
	
	int max_j = 30;
	
	lca(int n,vector<vector<int>> &E){
		depth.assign(E.size(),-1);
		parents.assign(E.size(),vector<int>(max_j,-1));
		
		stack<int> s;
		s.push(n);
		depth[n] = 0;
		while(s.size()!=0){
			int k = s.top();
			s.pop();
			for(int i=0;i<E[k].size();i++){
				int x = E[k][i];
				if(depth[x]!=-1)continue;
				s.push(x);
				depth[x] = depth[k]+1;
				for(int j=0;j<max_j;j++){
					if(j==0){
						parents[x][j] = k;
					}
					else{
						parents[x][j] = parents[parents[x][j-1]][j-1];
					}
					if(parents[x][j] == -1)break;
				}
			}
		}
	}
	
	//頂点uのk番目の親
	int kth_parent(int u,int k){
		for(int i=0;i<max_j;i++){
			if(k==0)break;
			if(u==-1)break;
			if(k%2){
				u = parents[u][i];
			}
			k/=2;
		}
		return u;
	}
	
	int query(int u,int v){
		if(depth[u]<depth[v])swap(u,v);
		u = kth_parent(u,depth[u]-depth[v]);
		
		if(u==v){
			return u;
		}
		
		for(int i=max_j-1;i>=0;i--){
			if(parents[u][i]!=parents[v][i]){
				u = parents[u][i];
				v = parents[v][i];
			}
		}
		
		return parents[u][0];
		
	}
	
	int get_distance(int u,int v){
		return depth[u]+depth[v]-2*depth[query(u,v)];
	}
	
	
};

int N,K,Q;
vector<int> dis;
vector<long long> calc;
vector<int> cnt;
vector<int> C;

void dfs(vector<vector<int>> &E,int now,int p){
	cnt[now] = C[now];
	for(int i=0;i<E[now].size();i++){
		dfs(E,E[now][i],now);
		cnt[now] += cnt[E[now][i]];
	}
}

void dfs2(vector<vector<int>> &E,int now,int p){
	if(p==-1){
		calc[now] = 0;
		for(int i=0;i<N;i++){
			calc[now] += (long long)dis[i] * C[i];
		}
	}
	else{
		calc[now] = calc[p];
		calc[now] -= cnt[now];
		calc[now] += K-cnt[now];
	}

	for(int i=0;i<E[now].size();i++){
		dfs2(E,E[now][i],now);
	}
}

void Erasedfs(vector<vector<int>> &E,int now,int p){
	vector<int> t;
	for(int i=0;i<E[now].size();i++){
		if(E[now][i]==p)continue;
		t.push_back(E[now][i]);
		Erasedfs(E,E[now][i],now);
	}
	E[now] = t;
}

int main(){
	
	cin>>N>>K>>Q;
	C.resize(N,0);
	vector<int> pos(K);
	for(int i=0;i<K;i++){
		scanf("%d",&pos[i]);
		pos[i]--;
		C[pos[i]]++;
	}
	
	vector<vector<int>> E(N);
	for(int i=0;i<N-1;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		a--;b--;
		E[a].push_back(b);
		E[b].push_back(a);
	}
	
	lca L(0,E);
	
	dis.resize(N);
	for(int i=0;i<N;i++){
		dis[i] = L.get_distance(0,i);
	}
	
	Erasedfs(E,0,-1);
	
	calc.resize(N);
	cnt.resize(N);
	dfs(E,0,-1);
	dfs2(E,0,-1);
	vector<pair<int,int>> Movement;
	for(int i=0;i<Q;i++){
		
		if(Movement.size()>100){
			for(int j=0;j<Movement.size();j++){
				C[pos[Movement[j].first]]--;
				pos[Movement[j].first] = Movement[j].second;
				C[pos[Movement[j].first]]++;
			}
			Movement.resize(0);
			dfs(E,0,-1);
			dfs2(E,0,-1);
		}
		
		int t;
		scanf("%d",&t);
		
		if(t==1){
			int p,d;
			scanf("%d %d",&p,&d);
			p--;d--;
			
			bool f = false;
			for(int j=0;j<Movement.size();j++){
				if(Movement[j].first==p){
					Movement[j].second = d;
					f=true;
					break;
				}
			}
			if(!f)Movement.emplace_back(p,d);
			
		}
		else{
			int e;
			scanf("%d",&e);
			e--;
			long long ans = calc[e];
			for(int j=0;j<Movement.size();j++){
				ans -= L.get_distance(e,pos[Movement[j].first]);
				ans += L.get_distance(e,Movement[j].second);
			}
			
			printf("%lld\n",ans);
			
		}
	}
	
	return 0;
}
0