Kod źródłowy zgłoszenia nr 926915

#include <bits/stdc++.h>
using namespace std;struct S{int z=0;vector<int>a,b;};struct X{int n,m;vector<vector<int>>g,h;vector<int>d,c,l;unordered_map<long long,S>p;static long long k(int u,int q){return(1LL*u<<32)^(unsigned)(q+1);}void w(vector<int>&o,const vector<int>&v,int x,int y){o.reserve(o.size()+v.size());for(int i:v)o.push_back(i==1?x:y+i-1);}const S&f(int u,int q){long long e=k(u,q);auto it=p.find(e);if(it!=p.end())return it->second;vector<int>s;s.reserve(h[u].size());for(int v:h[u])if(v!=q)s.push_back(v);struct C{int i;const S*s;};vector<C>r;r.reserve(s.size());int z=1;for(int v:s){const S&t=f(v,u);r.push_back({v,&t});z+=t.z;}sort(r.begin(),r.end(),[&](const C&x,const C&y){return x.s->b<y.s->b;});S y;y.z=z;bool aa=0;vector<int>a;if(l[u]>0){vector<int>v(l[u],1);int x=1,m=1;for(auto&o:r){w(v,o.s->b,x,m);m+=o.s->z;}v.push_back(m+1);a=move(v);aa=1;}for(auto&o:r){vector<int>v=o.s->a;int x=o.s->z+1,m=x;v.insert(v.end(),l[u],x);for(auto&j:r)if(j.i!=o.i){w(v,j.s->b,x,m);m+=j.s->z;}v.push_back(m+1);if(!aa||v<a){a=move(v);aa=1;}}y.a=move(a);bool bb=0;vector<int>b;if(l[u]>0){vector<int>v(l[u],2);int x=2,m=2;for(auto&o:r){w(v,o.s->b,x,m);m+=o.s->z;}v.push_back(1);b=move(v);bb=1;}for(auto&o:r){vector<int>v;v.reserve(o.s->a.size()+l[u]+4);for(int i:o.s->a)v.push_back(i+1);int x=o.s->z+2,m=x;v.insert(v.end(),l[u],x);for(auto&j:r)if(j.i!=o.i){w(v,j.s->b,x,m);m+=j.s->z;}v.push_back(1);if(!bb||v<b){b=move(v);bb=1;}}y.b=move(b);return p.emplace(e,move(y)).first->second;}vector<int>o(){if(m==1)return vector<int>(l[0]-1,1);bool ok=0;vector<int>a;for(int i=0;i<m;++i){if(!l[i])continue;struct C{int i;const S*s;};vector<C>r;r.reserve(h[i].size());for(int v:h[i]){const S&t=f(v,i);r.push_back({v,&t});}sort(r.begin(),r.end(),[&](const C&x,const C&y){return x.s->b<y.s->b;});int q=l[i]-1;bool aa=0;vector<int>b;if(q>0){vector<int>v(q,1);int x=1,m=1;for(auto&j:r){w(v,j.s->b,x,m);m+=j.s->z;}b=move(v);aa=1;}for(auto&j:r){vector<int>v=j.s->a;int x=j.s->z+1,m=x;v.insert(v.end(),q,x);for(auto&u:r)if(u.i!=j.i){w(v,u.s->b,x,m);m+=u.s->z;}if(!aa||v<b){b=move(v);aa=1;}}if(!ok||b<a){a=move(b);ok=1;}}return a;}void b(){c.assign(n,-1);vector<int>v;for(int i=0;i<n;++i)if(d[i]>1){c[i]=v.size();v.push_back(i);}m=v.size();l.assign(m,0);h.assign(m,{});for(int i=0;i<m;++i){int u=v[i];for(int j:g[u])if(d[j]==1)++l[i];else h[i].push_back(c[j]);}}};int main(){ios::sync_with_stdio(0);cin.tie(0);int t;cin>>t;while(t--){int n;cin>>n;X x;x.n=n;x.g.assign(n,{});x.d.assign(n,0);for(int i=0;i<n-1;++i){int a,b;cin>>a>>b;--a;--b;x.g[a].push_back(b);x.g[b].push_back(a);++x.d[a];++x.d[b];}x.b();x.p.reserve(max(4,4*x.m));vector<int>v=x.o();for(int i=0;i<(int)v.size();++i){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}return 0;}

1
2

#include <bits/stdc++.h>
using namespace std;struct S{int z=0;vector<int>a,b;};struct X{int n,m;vector<vector<int>>g,h;vector<int>d,c,l;unordered_map<long long,S>p;static long long k(int u,int q){return(1LL*u<<32)^(unsigned)(q+1);}void w(vector<int>&o,const vector<int>&v,int x,int y){o.reserve(o.size()+v.size());for(int i:v)o.push_back(i==1?x:y+i-1);}const S&f(int u,int q){long long e=k(u,q);auto it=p.find(e);if(it!=p.end())return it->second;vector<int>s;s.reserve(h[u].size());for(int v:h[u])if(v!=q)s.push_back(v);struct C{int i;const S*s;};vector<C>r;r.reserve(s.size());int z=1;for(int v:s){const S&t=f(v,u);r.push_back({v,&t});z+=t.z;}sort(r.begin(),r.end(),[&](const C&x,const C&y){return x.s->b<y.s->b;});S y;y.z=z;bool aa=0;vector<int>a;if(l[u]>0){vector<int>v(l[u],1);int x=1,m=1;for(auto&o:r){w(v,o.s->b,x,m);m+=o.s->z;}v.push_back(m+1);a=move(v);aa=1;}for(auto&o:r){vector<int>v=o.s->a;int x=o.s->z+1,m=x;v.insert(v.end(),l[u],x);for(auto&j:r)if(j.i!=o.i){w(v,j.s->b,x,m);m+=j.s->z;}v.push_back(m+1);if(!aa||v<a){a=move(v);aa=1;}}y.a=move(a);bool bb=0;vector<int>b;if(l[u]>0){vector<int>v(l[u],2);int x=2,m=2;for(auto&o:r){w(v,o.s->b,x,m);m+=o.s->z;}v.push_back(1);b=move(v);bb=1;}for(auto&o:r){vector<int>v;v.reserve(o.s->a.size()+l[u]+4);for(int i:o.s->a)v.push_back(i+1);int x=o.s->z+2,m=x;v.insert(v.end(),l[u],x);for(auto&j:r)if(j.i!=o.i){w(v,j.s->b,x,m);m+=j.s->z;}v.push_back(1);if(!bb||v<b){b=move(v);bb=1;}}y.b=move(b);return p.emplace(e,move(y)).first->second;}vector<int>o(){if(m==1)return vector<int>(l[0]-1,1);bool ok=0;vector<int>a;for(int i=0;i<m;++i){if(!l[i])continue;struct C{int i;const S*s;};vector<C>r;r.reserve(h[i].size());for(int v:h[i]){const S&t=f(v,i);r.push_back({v,&t});}sort(r.begin(),r.end(),[&](const C&x,const C&y){return x.s->b<y.s->b;});int q=l[i]-1;bool aa=0;vector<int>b;if(q>0){vector<int>v(q,1);int x=1,m=1;for(auto&j:r){w(v,j.s->b,x,m);m+=j.s->z;}b=move(v);aa=1;}for(auto&j:r){vector<int>v=j.s->a;int x=j.s->z+1,m=x;v.insert(v.end(),q,x);for(auto&u:r)if(u.i!=j.i){w(v,u.s->b,x,m);m+=u.s->z;}if(!aa||v<b){b=move(v);aa=1;}}if(!ok||b<a){a=move(b);ok=1;}}return a;}void b(){c.assign(n,-1);vector<int>v;for(int i=0;i<n;++i)if(d[i]>1){c[i]=v.size();v.push_back(i);}m=v.size();l.assign(m,0);h.assign(m,{});for(int i=0;i<m;++i){int u=v[i];for(int j:g[u])if(d[j]==1)++l[i];else h[i].push_back(c[j]);}}};int main(){ios::sync_with_stdio(0);cin.tie(0);int t;cin>>t;while(t--){int n;cin>>n;X x;x.n=n;x.g.assign(n,{});x.d.assign(n,0);for(int i=0;i<n-1;++i){int a,b;cin>>a>>b;--a;--b;x.g[a].push_back(b);x.g[b].push_back(a);++x.d[a];++x.d[b];}x.b();x.p.reserve(max(4,4*x.m));vector<int>v=x.o();for(int i=0;i<(int)v.size();++i){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}return 0;}