| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 555356 | urosk | Mergers (JOI19_mergers) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// __builtin_popcount(x)
// __builtin_popcountll(x)
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll int
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;
#define maxn 100005
ll n,k;
ll a[maxn];
ll dp[maxn][2];
ll b[maxn];
ll in[maxn];
ll out[maxn];
vector<ll> g[maxn];
vector<ll> v[maxn];
vector<ll> f[maxn];
ll ti = 1;
ll col = -1;
ll con[maxn];
ll dsu[maxn];
ll pari[maxn];
ll root(ll x){
while(x!=dsu[x]){
dsu[x] = dsu[dsu[x]];
x = dsu[x];
}
return x;
}
void upd(ll x,ll y){
x = root(x); y = root(y);
dsu[x] = y;
}
ll root2(ll x){
while(x!=con[x]){
con[x] = con[con[x]];
x = con[x];
}
return x;
}
void upd2(ll x,ll y){
x = root2(x); y = root2(y);
con[x] = y;
}
void updg(ll x,ll y){
upd2(x,y);
f[x].pb(y);
f[y].pb(x);
}
vector<vector<ll> > cnt;
bitset<maxn> st[maxn];
bitset<maxn> up[maxn];
void dfs(ll u,ll par){
st[u][b[u]] = 1;
pari[u] = par;
for(ll s : g[u]){
if(s==par) continue;
dfs(s,u);
st[u] |= st[s];
}
if(u==par) return;
up[u][b[par]] = 1;
up[u]|=up[par];
for(ll s : g[par]){
if(s==pari[u]) continue;
if(s==u) continue;
up[u]|=st[s];
}
if(up[u].count()+st[u].count()!=k) upd(par,u);
}
ll dis[maxn];
ll getnaj(ll u,ll par){
ll y = u;
for(ll s : f[u]){
if(s==par) continue;
dis[s] = dis[u] + 1;
ll e = getnaj(s,u);
if(dis[e]>dis[y]) y = e;
}
return y;
}
ll sizi = 0;
void brisi(ll u,ll par,ll x,vector<ll> w){
w.pb(u);
if(u==x){
for(ll i = 0;i<sz(w)-1;i++){
upd(w[i],w[i+1]);
}
sizi-=(sz(w)-1);
return;
}
for(ll s : f[u]){
if(s==par) continue;
brisi(s,u,x,w);
}
}
bool vis[maxn];
int main(){
ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
cin >> n >> k;
iota(dsu+1,dsu+n+1,1);
for(ll i = 1;i<=n-1;i++){
ll x,y; cin >> x >> y;
g[x].pb(y);
g[y].pb(x);
}
for(ll i = 1;i<=n;i++) cin >> b[i];
for(ll i = 1;i<=n;i++){
v[b[i]].pb(i);
}
dfs(1,1);
for(ll i = 1;i<=n;i++){
if(vis[root(i)]) continue;
vis[root(i)] = 1;
sizi++;
}
iota(con+1,con+n+1,1);
for(ll i = 1;i<=n;i++){
ll x = root(i);
for(ll j : g[i]){
ll y = root(j);
if(root2(x)==root2(y)) continue;
updg(x,y);
}
}
//for(ll i= 1;i<=n;i++) cerr<<root(i)<< " ";
//cerr<<endl;
ll ans = 0;
while(sizi>1){
/*
here;
for(ll i = 1;i<=n;i++){
if(sz(f[i])==0) continue;
cerr<<"i: "<<i<<endl;
for(ll x : f[i]) cerr<<x<< " ";
cerr<<endl;
}
*/
ll poc = 1;
for(ll i = 1;i<=n;i++) if(sz(f[i])>0) poc = i;
//cerr<<"poc: "<<poc<<endl;
fill(dis,dis+n+1,0);
dis[0] = llinf;
ll x = getnaj(poc,poc);
//cerr<<x<<endl;
fill(dis,dis+n+1,0);
dis[0] = llinf;
ll y = getnaj(x,x);
brisi(x,x,y,{});
//cerr<<y<<endl;
for(ll i = 1;i<=n;i++) f[i].clear();
iota(con+1,con+n+1,1);
for(ll i = 1;i<=n;i++){
ll x = root(i);
for(ll j : g[i]){
ll y = root(j);
if(root2(x)==root2(y)) continue;
updg(x,y);
}
}
ans++;
}
cout<<ans<<endl;
return 0;
}
/*
5 4
1 2
2 3
3 4
3 5
1
2
1
3
4
*/