Submission #1294322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294322		Piokemon	Unique Cities (JOI19_ho_t5)	C++20	100 / 100	368 ms	33932 KiB

joi2019_ho_t5

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

constexpr int N = 2e5;
int a[N+9];
vector<int> graf[N+9];
int ans[N+9];
int cnt[N+9];
vector<pair<int,int>> stos;
int dpt[N+9];
int maxdpt[N+9];
int terans=0;

void add(int v){
    if (!cnt[a[v]]){
        terans++;
    }
    stos.push_back({dpt[v],v});
    cnt[a[v]]++;
}

void usun(){
    if (stos.empty())return;
    int v=stos.back().second; stos.pop_back();
    cnt[a[v]]--;
    if (cnt[a[v]]==0)terans--;
}

void dfs1(int v, int p){
    maxdpt[v]=dpt[v];
    for (int x:graf[v]){
        if (x==p)continue;
        dpt[x]=dpt[v]+1;
        dfs1(x,v);
        maxdpt[v]=max(maxdpt[v],maxdpt[x]);
    }
}

void calc(int v, int p){
    pair<int,int> maks={0,0};
    for (int x:graf[v]){
        if (x==p)continue;
        int te=x;
        if (maxdpt[maks.first]<maxdpt[te])swap(te,maks.first);
        if (maxdpt[maks.second]<maxdpt[te])swap(te,maks.second);
    }
    if (maks.first==0){ans[v]=max(ans[v],terans);return;}
    if (maks.second==0){
        add(v);
        
        calc(maks.first,v);

        int minidpt=dpt[v] - (maxdpt[maks.first]-dpt[v]);
        while (!stos.empty() && stos.back().first>=minidpt)usun();
        ans[v]=max(ans[v],terans);
        return;
    }
    int minidpt = dpt[v] - (maxdpt[maks.second]-dpt[v]);
    while (!stos.empty() && stos.back().first>=minidpt)usun();
    add(v);
    calc(maks.first,v);
    minidpt=dpt[v] - (maxdpt[maks.first]-dpt[v]);
    while (!stos.empty() && stos.back().first>=minidpt)usun();

    for (int x:graf[v]){
        if (x==p || x==maks.first)continue;
        add(v);
        calc(x,v);
    }
    while(!stos.empty() && stos.back().first>=dpt[v])usun();
    ans[v]=max(ans[v],terans);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,k,u,b;
    cin >> n >> k;
    for (int x=1;x<n;x++){
        cin >> u >> b;
        graf[u].push_back(b);
        graf[b].push_back(u);
    }
    for (int x=1;x<=n;x++) cin >> a[x];
    dfs1(1,-1);
    int l=1,r=1;
    for (int x=1;x<=n;x++){
        ans[x]=0;
        if (dpt[x]>dpt[l])l=x;
    }
    dpt[l]=0;
    dfs1(l,-1);
    calc(l,-1);

    while(!stos.empty())usun();

    for (int x=1;x<=n;x++){
        if (dpt[x]>dpt[r])r=x;
    }
    dpt[r]=0;
    dfs1(r,-1);

    calc(r,-1);
    for (int x=1;x<=n;x++) cout << ans[x] << '\n';
}

• Subtask 1: 4 / 4
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32