結果
| 問題 | No.1295 木と駒 |
| ユーザー |
 沙耶花
|
| 提出日時 | 2020-05-20 23:47:48 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,173 ms / 2,000 ms |
| コード長 | 6,636 bytes |
| コンパイル時間 | 4,348 ms |
| コンパイル使用メモリ | 233,640 KB |
| 最終ジャッジ日時 | 2025-01-10 13:29:43 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 48 |
コンパイルメッセージ
main.cpp:189:25: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
189 | int get_dis(int u,int v,auto &H,auto &S){
| ^~~~
main.cpp:189:33: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
189 | int get_dis(int u,int v,auto &H,auto &S){
| ^~~~
main.cpp:201:11: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
201 | void dfs0(auto &E,int now,int p,auto &H,auto &S1,auto &S2){
| ^~~~
main.cpp:201:33: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
201 | void dfs0(auto &E,int now,int p,auto &H,auto &S1,auto &S2){
| ^~~~
main.cpp:201:41: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
201 | void dfs0(auto &E,int now,int p,auto &H,auto &S1,auto &S2){
| ^~~~
main.cpp:201:50: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
201 | void dfs0(auto &E,int now,int p,auto &H,auto &S1,auto &S2){
| ^~~~
main.cpp:217:11: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
217 | void dfs1(auto &E,int now,int p,auto &H,auto &S0,auto &S1,auto &S2){
| ^~~~
main.cpp:217:33: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
217 | void dfs1(auto &E,int now,int p,auto &H,auto &S0,auto &S1,auto &S2){
| ^~~~
main.cpp:217:41: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
217 |
ソースコード
#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;
int target = -1;
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);
target = to;
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){
bool F = false;
if(target == now){
F=true;
target = -1;
int maxi = -1;
for(int i=0;i<N;i++){
for(int j=0;j<E[i].size();j++){
int from = i;
int to = E[i][j];
int ind = H.pos[mp[{from,to}]];
if(S1.query(ind,ind+1)==1){
if(get_dis(now,from,H,S0)>get_dis(now,to,H,S0))swap(from,to);
int d = get_dis(now,to,H,S0);
if(d>maxi){
maxi = d;
target = to;
}
}
}
}
}
if(target==-1){
ans[now] = true;
}
else{
int d1 = get_dis(now,target,H,S0);
int d2 = get_dis(now,target,H,S1);
int d3 = get_dis(now,target,H,S2);
if(d2==cnt&&d1==d3){
ans[now]=true;
}
}
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;
bool FF = false;
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);
if(target==-1){
FF = true;
target = now;
}
}
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(FF){
target = -1;
}
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]);
}
if(F)target = now;
}
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;
}