結果

問題 No.1295 木と駒
ユーザー 沙耶花沙耶花
提出日時 2020-05-21 00:26:42
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 6,018 bytes
コンパイル時間 3,274 ms
コンパイル使用メモリ 242,228 KB
実行使用メモリ 53,960 KB
最終ジャッジ日時 2024-07-04 18:33:17
合計ジャッジ時間 7,329 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,624 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 22 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 1 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 TLE -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:188:25: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  188 | int get_dis(int u,int v,auto &H,auto &S){
      |                         ^~~~
main.cpp:188:33: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  188 | int get_dis(int u,int v,auto &H,auto &S){
      |                                 ^~~~
main.cpp:200:11: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  200 | void dfs0(auto &E,int now,int p,auto &H,auto &S1,auto &S2){
      |           ^~~~
main.cpp:200:33: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  200 | void dfs0(auto &E,int now,int p,auto &H,auto &S1,auto &S2){
      |                                 ^~~~
main.cpp:200:41: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  200 | void dfs0(auto &E,int now,int p,auto &H,auto &S1,auto &S2){
      |                                         ^~~~
main.cpp:200:50: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  200 | void dfs0(auto &E,int now,int p,auto &H,auto &S1,auto &S2){
      |                                                  ^~~~
main.cpp:215:11: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  215 | void dfs1(auto &E,int now,int p,auto &H,auto &S0,auto &S1,auto &S2){
      |           ^~~~
main.cpp:215:33: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  215 | void dfs1(auto &E,int now,int p,auto &H,auto &S0,auto &S1,auto &S2){
      |                                 ^~~~
main.cpp:215:41: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  215 | void dfs1(auto &E,int now,int p,auto &H,auto &S0,auto &S1,auto &S2){
      |

ソースコード

diff # 

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

struct HLD{
	vector<int> sz,parent,depth,root,pos;
	vector<int> arr;
	HLD(vector<vector<int>> &E){
		sz.resize(E.size(),1);
		parent.resize(E.size(),0);
		depth.resize(E.size(),0);
		root.resize(E.size(),0);
		pos.resize(E.size(),0);
		
		dfs(0,-1,E);
		dfs2(0,-1,E,0);
	}
	
	void dfs(int now,int p,vector<vector<int>> &E){
		parent[now] = p;
		if(p==-1){
			depth[now] = 0;
		}
		else{
			depth[now] = depth[p]+1;
		}
		for(int i=0;i<E[now].size();i++){
			int to = E[now][i];
			if(to==p)continue;
			dfs(to,now,E);
			sz[now] += sz[to];
		}
	}
	
	void dfs2(int now,int p,vector<vector<int>> &E,int r){
		pos[now] = arr.size();
		arr.push_back(now);
		root[now] = r;
		int maxi = 0;
		int ind = -1;
		for(int i=0;i<E[now].size();i++){
			int to = E[now][i];
			if(to==p)continue;
			if(maxi<sz[to]){
				maxi = sz[to];
				ind = to;
			}
		}
		if(ind==-1)return;
		dfs2(ind,now,E,r);
		for(int i=0;i<E[now].size();i++){
			int to = E[now][i];
			if(to==p||to==ind)continue;
			dfs2(to,now,E,to);
		}
	}
	
	vector<pair<int,int>> query(int u,int v){
		vector<pair<int,int>> ret;
		int t = 0;
		while(root[u]!=root[v]){
			if(depth[root[u]] <= depth[root[v]]){
				ret.insert(ret.begin()+t,{pos[root[v]], pos[v]});
				v = parent[root[v]];
			}
			else{
				ret.insert(ret.begin()+t,{pos[u],pos[root[u]]});
				u = parent[root[u]];
				t++;
			}
		}
		ret.insert(ret.begin()+t,{pos[u],pos[v]});
		return ret;
	}
	
};

template <typename T,typename F>
struct segtree{
	F func;
	vector<T> v;
	int n;
	
	T init_value;
	
	segtree(int sz,F f,T iv):func(f){
		init_value = iv;
		n=1;
		while(true){
			if(n>=sz)break;
			n*=2;
		}
		v.resize(2*n,init_value);

		for(int i=n-1;i>=0;i--){
			v[i]=func(v[i<<1],v[(i<<1)+1]);
		}
	}
	
	segtree(vector<T> &x,F f,T iv):func(f){
		init_value = iv;
		n=1;
		while(true){
			if(n>=x.size())break;
			n*=2;
		}
		v.resize(2*n,init_value);
		
		for(int i=0;i<x.size();i++){
			v[n+i]=x[i];
		}
		for(int i=n-1;i>=0;i--){
			v[i]=func(v[i<<1],v[(i<<1)+1]);
		}
	}

	void update(int x,T val){
		x+=n;
		v[x]=val;
		while(x>0){
			x>>=1;
			v[x]=func(v[x<<1],v[(x<<1)+1]);
		}
	}
	
	T query(int l,int r){
		if(l>=r)return init_value;
		l+=n;
		r+=n;
		T res1 = init_value;
		T res2 = init_value;
		while(true){
			if(l&1){
				res1=func(res1,v[l++]);
			}
			if(r&1){
				res2=func(v[--r],res2);
			}
			if(l>=r)break;
			l>>=1;r>>=1;
		}
		return func(res1,res2);
	}
	
	void show(){
		int n = 1;
		for(int i=1;i<v.size();i++){
			for(int j=0;j<n;j++){
				if(j!=0)cout<<' ';
				cout<<v[i+j];
			}
			cout<<endl;
			i+=n-1;
			n*=2;
		}
	}
	
};

int N;
vector<vector<int>> E;
int cnt = 0;

map<pair<int,int>,int> mp;
vector<bool> ans;

vector<vector<int>> get_fixedE(vector<vector<int>> E){
	vector<vector<int>> ret(2*N-1,vector<int>());
	int t = N;
	for(int i=0;i<N;i++){
		for(int j=0;j<E[i].size();j++){
			int to = E[i][j];
			if(i>to)continue;
			mp[{i,to}]=t;
			mp[{to,i}]=t;
			ret[i].push_back(t);
			ret[t].push_back(i);
			ret[to].push_back(t);
			ret[t].push_back(to);
			t++;
		}
	}
	return ret;
}

int get_dis(int u,int v,auto &H,auto &S){
	auto V = H.query(u,v);
	int ret = 0;
	for(auto a:V){
		int l = a.first;
		int r = a.second;
		if(l>r)swap(l,r);
		ret += S.query(l,r+1);
	}
	return ret;
}

void dfs0(auto &E,int now,int p,auto &H,auto &S1,auto &S2){
	for(int i=0;i<E[now].size();i++){
		int to = E[now][i];
		if(to==p)continue;
		if(E[to][0]!=now){
			S1.update(H.pos[mp[{now,to}]],1);
			cnt++;
		}
		if(E[now][0]==to||i+1==E[now].size()||(i+2==E[now].size()&&E[now].back()==p)){
			S2.update(H.pos[mp[{now,to}]],1);
		}
		dfs0(E,to,now,H,S1,S2);
	}
}

void dfs1(auto &E,int now,int p,auto &H,auto &S0,auto &S1,auto &S2){

	for(int i=0;i<N;i++){
		int d1 = get_dis(now,i,H,S0);
		int d2 = get_dis(now,i,H,S1);
		int d3 = get_dis(now,i,H,S2);
		
		
		if(d2==cnt&&d1==d3){
			ans[now]=true;
			break;
		}
	}
	
	vector<int> Temp;
	for(int i=0;i<E[now].size();i++){
		int to = E[now][i];
		int n = mp[{now,to}];
		int fn = H.pos[n];
		
		Temp.push_back(S2.query(fn,fn+1));
		if(i==0||i+1==E[now].size())S2.update(fn,1);
		else S2.update(fn,0);
	}
	
	for(int i=0;i<E[now].size();i++){
		int to = E[now][i];
		if(to==p)continue;
		int n = mp[{now,to}];
		int fn = H.pos[n];

		if(S1.query(fn,fn+1)==1)cnt--;
		S1.update(fn,0);
		if(E[now][0]!=to){
			cnt++;
			S1.update(fn,1);
		}
		
		vector<int> temp;
		for(int j=0;j<E[to].size();j++){
			int x = H.pos[mp[{to,E[to][j]}]];
			temp.push_back(S2.query(x,x+1));
			S2.update(x,0);
			if(j==0||j+1==E[to].size())S2.update(x,1);
		}
		
		if(i+1==E[now].size()&&E[now].size()>=2){
			int x = E[now][i-1];
			int nn = mp[{now,x}];
			int fnn = H.pos[nn];
			S2.update(fnn,1);
		}
		
		dfs1(E,to,now,H,S0,S1,S2);
		
		if(S1.query(fn,fn+1)==1)cnt--;
		S1.update(fn,0);
		if(E[to][0]!=now){
			cnt++;
			S1.update(fn,1);
		}
		
		for(int j=0;j<E[to].size();j++){
			int x = H.pos[mp[{to,E[to][j]}]];
			S2.update(x,temp[j]);
		}
		
		
		
	}
	
	
	for(int i=0;i<E[now].size();i++){
		int to = E[now][i];
		int n = mp[{now,to}];
		int fn = H.pos[n];
		
		S2.update(fn,Temp[i]);
	}
	
	
}

int main(){
	
	scanf("%d",&N);
	
	E.resize(N,vector<int>());
	
	for(int i=0;i<N-1;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		u--;v--;
		E[u].push_back(v);
		E[v].push_back(u);
	}
	
	
	
	for(int i=0;i<N;i++)sort(E[i].begin(),E[i].end());
	
	vector<vector<int>> fixedE = get_fixedE(E);
		
	HLD H(fixedE);
	
	vector<int> d0(2*N-1,0);
	vector<int> d1 = d0,d2 = d0;
	
	for(int i=N;i<2*N-1;i++)d0[i] = 1;
	
	{
		vector<int> temp(2*N-1);
		for(int i=0;i<2*N-1;i++){
			temp[i] = d0[H.arr[i]];
		}
		d0 = temp;
	}
	
	auto f = [](int a,int b){
		return a+b;
	};
	
	segtree<int,decltype(f)> S0(d0,f,0),S1(d1,f,0),S2(d2,f,0);
	
	dfs0(E,0,-1,H,S1,S2);
	
	ans.resize(N,false);
	
	dfs1(E,0,-1,H,S0,S1,S2);
	
	for(int i=0;i<N;i++){
		if(ans[i])printf("Yes\n");
		else printf("No\n");
	}
	
	
	return 0;	
}
0