#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define st first
#define nd second
#define sp " "
#define endl "\n"
#define pii pair<int, int>
#define N 200005
const int modulo = 1e9 + 7;
int dist[N], ans[N], dep[N], arr[N], cnt[N], res;
vector<int> adj[N];
vector<int> s;
void del(int x)
{
while(!s.empty() && dist[s.back()] >= x)
{
int curr = s.back();
cnt[arr[curr]]--;
if (cnt[arr[curr]] == 0) res--;
s.pop_back();
}
}
void add(int node)
{
if (s.empty() || s.back() != node)
{
s.pb(node);
cnt[arr[node]]++;
if (cnt[arr[node]] == 1) res++;
}
}
void dfs(int node, int root, int d)
{
dist[node] = d;
dep[node] = d;
for (auto i : adj[node])
{
if (i != root) dfs(i, node, d + 1);
dep[node] = max(dep[node], dep[i]);
}
}
void dfs2(int node, int root)
{
pair<pii, pii> maks = {{0, 0}, {0, 0}};
for (int i = 0; i < adj[node].size(); i++)
{
int curr = adj[node][i];
if (curr == root) continue;
if (dep[node] > maks.st.st)
{
maks.nd = maks.st;
maks.st = {dep[curr], curr};
}
else maks.nd = max(maks.nd, {dep[curr], curr});
}
int diff = maks.nd.st - dist[node];
int to = max(0, dist[node] - diff);
del(to);
int top = maks.st.nd;
add(node);
if (top != 0) dfs2(top, node);
diff = maks.st.st - dist[node];
to = max(0, dist[node] - diff);
del(to);
for (int i = 0; i < adj[node].size(); i++)
{
int curr = adj[node][i];
if (curr != root && curr != top)
{
add(node);
dfs2(curr, node);
}
}
del(dist[node]);
ans[node] = max(ans[node], res);
}
int32_t main()
{
fastio();
int n, m;
cin>>n>>m;
for (int i = 1; i < n; i++)
{
int u, v;
cin>>u>>v;
adj[u].pb(v);
adj[v].pb(u);
}
for (int i = 1; i <= n; i++)
cin>>arr[i];
dfs(1, 0, 1);
pii maks = {0, 0};
for (int i = 1; i <= n; i++) maks = max(maks, {dist[i], i});
int root = maks.nd;
//cerr<<root<<endl;
dfs(root, 0, 1);
dfs2(root, 0);
//for (int i = 1; i <= n; i++)
// cout<<ans[i]<<sp;
//cout<<endl;
s.clear();
res = 0;
maks = {0, 0};
for (int i = 1; i <= n; i++) maks = max(maks, {dist[i], i});
root = maks.nd;
dfs(root, 0, 1);
dfs2(root, 0);
for (int i = 1; i <= n; i++)
cout<<ans[i]<<endl;
cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}
Compilation message
joi2019_ho_t5.cpp: In function 'void dfs2(int, int)':
joi2019_ho_t5.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i = 0; i < adj[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int i = 0; i < adj[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
10732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
197 ms |
13428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
