結果

問題 No.1197 モンスターショー
コンテスト
ユーザー define
提出日時 2020-08-05 20:30:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 4,280 bytes
コンパイル時間 5,930 ms
コンパイル使用メモリ 213,976 KB
最終ジャッジ日時 2025-01-12 15:08:15
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40 WA * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘void HLD::make_path(int, int, int)’:
main.cpp:106:25: warning: ‘mxidx’ may be used uninitialized [-Wmaybe-uninitialized]
  106 |                         if(mxidx==i){
      |                         ^~
main.cpp:99:21: note: ‘mxidx’ was declared here
   99 |                 int mxidx,mx=0;
      |                     ^~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()

template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 1e9+7;
//constexpr int inf = 3e18;
template<typename Monoid,typename OperatorMonoid,typename F,typename G,typename H>
struct Segtree{
	int size=1;
	vector<Monoid>dat;
	vector<OperatorMonoid>lazy;
	const F f;
	const G g;
	const H h;
	Monoid M;
	OperatorMonoid OM;
	void set(int a,Monoid x){
		dat[a+size-1]=x;
	}
	void init(){
		for(int i=size-2;i>=0;i--){
			dat[i]=f(dat[i*2+1],dat[i*2+2]);
		}
	}
	void eval(int k,int l,int r){
		if(lazy[k]!=OM){
			dat[k]=g(dat[k],lazy[k],(r-l));
			if(r-l>1){
				lazy[2*k+1]=h(lazy[2*k+1],lazy[k]);
				lazy[2*k+2]=h(lazy[2*k+2],lazy[k]);
			}
			lazy[k]=OM;
		}
	}
	void update(int a,int b,OperatorMonoid M,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l)return;
		if(a<=l&&r<=b){
			lazy[k]=h(lazy[k],M);
			eval(k,l,r);
			return;
		}
		update(a,b,M,k*2+1,l,(l+r)/2);
		update(a,b,M,k*2+2,(l+r)/2,r);
		dat[k]=f(dat[k*2+1],dat[k*2+2]);
	}
	Monoid query(int a,int b,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l)return M;
		if(a<=l&&r<=b)return dat[k];
		Monoid lv=query(a,b,k*2+1,l,(l+r)/2);
		Monoid rv=query(a,b,k*2+2,(l+r)/2,r);
		return f(lv,rv);
	}
	Segtree(int x,F f,G g,H h,Monoid M,OperatorMonoid OM)
	:f(f),g(g),h(h),M(M),OM(OM){
		while(size<x)size*=2;
		dat.resize(size*2-1,M);
		lazy.resize(size*2-1,OM);
	}
};
struct HLD{
	using V=vector<pair<int,P>>;
	struct heavy_set{
		vector<int>ele;
		int depth,par,cost1=0,cost2=0;
		heavy_set(int v,int d,int par)
		:ele(1,v),depth(d),par(par){}
	};
	vector<vector<int>>G;
	vector<heavy_set>S;
	vector<int>subsize,stidx,eleidx;
	int subtree(int v,int p){
		int &sz=subsize[v];
		if(sz)return sz;
		sz=1;
		for(int i:G[v])if(i!=p)sz+=subtree(i,v);
		return sz;
	}
	void make_path(int v,int p,int id){
		stidx[v]=id;
		eleidx[v]=S[id].ele.size()-1;
		int mxidx,mx=0;
		for(int i:G[v])if(i!=p){
			if(mx<subtree(i,v)){
				mx=subtree(i,v);mxidx=i;
			}
		}
		for(int i:G[v])if(i!=p){
			if(mxidx==i){
				S[id].ele.push_back(i);
				make_path(i,v,id);
			}else {
				S.emplace_back(i,S[id].depth+1,v);
				make_path(i,v,S.size()-1);
			}
		}
	}
	int st(int v){return stidx[v];}
	int el(int v){return eleidx[v];}
	HLD(vector<vector<int>>&G):G(G){
		int N=G.size();
		subsize.resize(N);
		eleidx.resize(N);
		stidx.resize(N);
		S.emplace_back(0,0,0);
		make_path(0,0,0);
	}
};
int N,K,Q;
int C[100005],par[100005],cnt[100005],dis[100005];
vector<vector<int>>G;
void dfs(int x,int p){
	if(p)par[x]=par[p];
	else par[x]=x;
	for(int i:G[x])if(i!=p){
		dis[i]=dis[x]+1;
		dfs(i,x);
	}
}
signed main(){
	cin>>N>>K>>Q;G.resize(N);
	rep(i,K){cin>>C[i];C[i]--;}
	rep(i,N-1){
		int a,b;cin>>a>>b;a--;b--;
		G[a].push_back(b);G[b].push_back(a);
	}
	dfs(0,0);
	HLD hld(G);
	auto f=[](int a,int b){return a+b;};
	auto g=[](int a,int b,int sz){return a+b*sz;};
	auto h=[](int a,int b){return a+b;};
	vector<Segtree<int,int,decltype(f),decltype(g),decltype(h)>>segtrees;
	rep(i,len(hld.S))segtrees.emplace_back(len(hld.S[i].ele),f,g,h,0,0);
	auto add=[&](int a,int x){
		while(hld.st(a)!=0){
			segtrees[hld.st(a)].update(0,hld.el(a),x);
			hld.S[hld.st(a)].cost1+=x;
			a=hld.S[hld.st(a)].par;
		}
		segtrees[0].update(0,hld.el(a),x);
	};
	auto query=[&](int a){
		int res=0;
		while(hld.st(a)!=0){
			res+=segtrees[hld.st(a)].query(0,hld.el(a));
			res+=hld.S[hld.st(a)].cost1;
			a=hld.S[hld.st(a)].par;
		}
		return res+segtrees[0].query(0,hld.el(a));
	};
	int ans=0;
	rep(i,K){
		add(C[i],1);
		cnt[par[C[i]]]++;
		ans+=dis[C[i]];
	}
	for(auto i:segtrees)i.init();
	while(Q--){
		int type;cin>>type;
		if(type==1){
			int p,d;cin>>p>>d;p--;d--;
			add(C[p],-1);add(d,1);
			ans-=dis[C[p]];ans+=dis[d];
			cnt[par[C[p]]]--;cnt[par[d]]++;
			C[p]=d;
		}else {
			int e;cin>>e;e--;
			int res=ans;
			res-=query(e)*2;
			res+=dis[e]*K;
			cout<<res<<"\n";
		}
	}
}
0