yukicoder : No.3222 Let the World Forget Me

これは割と素直に行けた。
https://yukicoder.me/problems/no/3222

問題

木を成すN点の無向グラフが与えられる。
各点vには、異なる値P[v]が設定されている。
時刻0において、うちM個の点が汚染されており、入力で与えられる。

時間が1経つごとに、以下が行われる。

• 汚染されていない頂点vのうち、葉となるものの中でP[v]が最大となる点とその隣接辺が取り除かれる。
• 汚染されている頂点に対し、隣接する頂点のうちまだ汚染されていない頂点が汚染される

取り除かれる頂点vのP[v]の総和を求めよ。

解法

問題に従い愚直にシミュレートすればよい。
汚染の伝搬は、各頂点1回しかやる必要がないので、均しでO(N)回で済む。

int N,M;
int P[101010],T[101010];
set<int> E[101010],E2[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>P[i];
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].insert(y-1);
		E[y-1].insert(x-1);
		E2[x-1].insert(y-1);
		E2[y-1].insert(x-1);
	}
	FOR(i,M) {
		cin>>x;
		T[x-1]=1;
	}
	priority_queue<pair<int,int>> PQ;
	queue<int> TQ;
	FOR(i,N) {
		if(T[i]==1) TQ.push(i);
		if(T[i]==0&&E[i].size()==1) PQ.push({P[i],i});
	}
	ll ret=0;
	FOR(i,N) {
		while(PQ.size()) {
			x=PQ.top().second;
			PQ.pop();
			if(T[x]) continue;
			ret+=P[x];
			y=*E[x].begin();
			E[y].erase(x);
			T[x]=-1;
			if(E[y].size()==1&&T[y]==0) PQ.push({P[y],y});
			break;
		}
		queue<int> NQ;
		while(TQ.size()) {
			x=TQ.front();
			TQ.pop();
			FORR(e,E2[x]) if(T[e]==0) {
				T[e]=1;
				NQ.push(e);
			}
			
		}
		TQ=NQ;
	}
	cout<<ret<<endl;
}

まとめ

素直にシミュレートすれば済むので、★2.5でも良いかもとは思った。