#include <bits/stdc++.h>
using namespace std;
const int Nmax = 2e5 + 5;
int down[Nmax], ans[Nmax], level[Nmax], st[Nmax], max_ex[Nmax];
bool ap[Nmax];
vector<int> v[Nmax];
int n, M;
int tip[Nmax];
void read()
{
int i, x, y;
cin >> n >> M;
for(i=1; i<n; ++i)
{
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
for(i=1; i<=n; ++i) cin >> tip[i];
}
void print_sol()
{
int i;
for(i=1; i<=n; ++i) cout << ans[i] << '\n';
}
void max_to(int &x, int y) { if(x < y) x = y; }
void dfs0(int node, int dad = 0)
{
level[node] = level[dad] + 1;
for(auto it : v[node])
if(it != dad)
dfs0(it, node);
}
pair<int,int> diametru()
{
int i, A = 1, B = 1;
dfs0(1);
for(i=1; i<=n; ++i)
if(level[i] > level[A]) A = i;
dfs0(A);
for(i=1; i<=n; ++i)
if(level[i] > level[B]) B = i;
return {A, B};
}
void dfs(int node, int dad = 0)
{
down[node] = 1;
level[node] = level[dad] + 1;
for(auto it : v[node])
if(it != dad)
{
dfs(it, node);
down[node] = max(down[node], down[it] + 1);
}
int i, mx = 0;
for(i=0; i<v[node].size(); ++i)
if(v[node][i] != dad)
{
max_ex[v[node][i]] = mx;
max_to(mx, down[v[node][i]]);
}
mx = 0;
for(i=v[node].size()-1; i>=0; --i)
if(v[node][i] != dad)
{
max_to(max_ex[v[node][i]], mx);
max_to(mx, down[v[node][i]]);
}
}
int cnt_dist(vector<int> &v)
{
for(auto it : v) ap[tip[it]] = 1;
int i, ans = 0;
for(i=1; i<=M; ++i)
if(ap[i])
{
++ans;
ap[i] = 0;
}
return ans;
}
void solve(int node, vector<int> &stramos, int dad = 0)
{
int i;
vector<int> see;
for(i=0; i<stramos.size(); ++i)
if(level[stramos[i]] <= level[node] - down[node])
see.push_back(stramos[i]);
max_to(ans[node], cnt_dist(see));
//stramos.push_back(node);
for(auto it : v[node])
if(it != dad)
{
vector<int> act = stramos;
while(act.size() && level[act.back()] >= level[node] - max_ex[it]) act.pop_back();
act.push_back(node);
solve(it, act, node);
}
}
void Solve(int node)
{
dfs(node);
vector<int> V;
solve(node, V);
}
int main()
{
// freopen("input", "r", stdin);
cin.sync_with_stdio(false);
read();
// dfs(1);
auto P = diametru();
Solve(P.first);
Solve(P.second);
print_sol();
return 0;
}
Compilation message
joi2019_ho_t5.cpp: In function 'void dfs(int, int)':
joi2019_ho_t5.cpp:74:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<v[node].size(); ++i)
~^~~~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'void solve(int, std::vector<int>&, int)':
joi2019_ho_t5.cpp:109:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<stramos.size(); ++i)
~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5120 KB |
Output is correct |
2 |
Correct |
11 ms |
5248 KB |
Output is correct |
3 |
Correct |
23 ms |
10368 KB |
Output is correct |
4 |
Correct |
18 ms |
7364 KB |
Output is correct |
5 |
Correct |
8 ms |
5120 KB |
Output is correct |
6 |
Correct |
64 ms |
25976 KB |
Output is correct |
7 |
Correct |
21 ms |
7808 KB |
Output is correct |
8 |
Correct |
11 ms |
5120 KB |
Output is correct |
9 |
Correct |
10 ms |
5248 KB |
Output is correct |
10 |
Correct |
10 ms |
5248 KB |
Output is correct |
11 |
Correct |
8 ms |
5248 KB |
Output is correct |
12 |
Correct |
8 ms |
5120 KB |
Output is correct |
13 |
Correct |
81 ms |
22964 KB |
Output is correct |
14 |
Correct |
13 ms |
6556 KB |
Output is correct |
15 |
Correct |
12 ms |
5900 KB |
Output is correct |
16 |
Correct |
7 ms |
5120 KB |
Output is correct |
17 |
Correct |
38 ms |
15232 KB |
Output is correct |
18 |
Correct |
22 ms |
7700 KB |
Output is correct |
19 |
Correct |
10 ms |
5120 KB |
Output is correct |
20 |
Correct |
88 ms |
26004 KB |
Output is correct |
21 |
Correct |
25 ms |
7772 KB |
Output is correct |
22 |
Correct |
11 ms |
5120 KB |
Output is correct |
23 |
Correct |
15 ms |
5248 KB |
Output is correct |
24 |
Correct |
13 ms |
5248 KB |
Output is correct |
25 |
Correct |
10 ms |
5120 KB |
Output is correct |
26 |
Correct |
9 ms |
5120 KB |
Output is correct |
27 |
Correct |
45 ms |
13732 KB |
Output is correct |
28 |
Correct |
38 ms |
12288 KB |
Output is correct |
29 |
Correct |
23 ms |
6440 KB |
Output is correct |
30 |
Correct |
12 ms |
5248 KB |
Output is correct |
31 |
Correct |
42 ms |
15228 KB |
Output is correct |
32 |
Correct |
29 ms |
7704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
335 ms |
12792 KB |
Output is correct |
2 |
Runtime error |
619 ms |
275456 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2051 ms |
16500 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5120 KB |
Output is correct |
2 |
Correct |
11 ms |
5248 KB |
Output is correct |
3 |
Correct |
23 ms |
10368 KB |
Output is correct |
4 |
Correct |
18 ms |
7364 KB |
Output is correct |
5 |
Correct |
8 ms |
5120 KB |
Output is correct |
6 |
Correct |
64 ms |
25976 KB |
Output is correct |
7 |
Correct |
21 ms |
7808 KB |
Output is correct |
8 |
Correct |
11 ms |
5120 KB |
Output is correct |
9 |
Correct |
10 ms |
5248 KB |
Output is correct |
10 |
Correct |
10 ms |
5248 KB |
Output is correct |
11 |
Correct |
8 ms |
5248 KB |
Output is correct |
12 |
Correct |
8 ms |
5120 KB |
Output is correct |
13 |
Correct |
81 ms |
22964 KB |
Output is correct |
14 |
Correct |
13 ms |
6556 KB |
Output is correct |
15 |
Correct |
12 ms |
5900 KB |
Output is correct |
16 |
Correct |
7 ms |
5120 KB |
Output is correct |
17 |
Correct |
38 ms |
15232 KB |
Output is correct |
18 |
Correct |
22 ms |
7700 KB |
Output is correct |
19 |
Correct |
10 ms |
5120 KB |
Output is correct |
20 |
Correct |
88 ms |
26004 KB |
Output is correct |
21 |
Correct |
25 ms |
7772 KB |
Output is correct |
22 |
Correct |
11 ms |
5120 KB |
Output is correct |
23 |
Correct |
15 ms |
5248 KB |
Output is correct |
24 |
Correct |
13 ms |
5248 KB |
Output is correct |
25 |
Correct |
10 ms |
5120 KB |
Output is correct |
26 |
Correct |
9 ms |
5120 KB |
Output is correct |
27 |
Correct |
45 ms |
13732 KB |
Output is correct |
28 |
Correct |
38 ms |
12288 KB |
Output is correct |
29 |
Correct |
23 ms |
6440 KB |
Output is correct |
30 |
Correct |
12 ms |
5248 KB |
Output is correct |
31 |
Correct |
42 ms |
15228 KB |
Output is correct |
32 |
Correct |
29 ms |
7704 KB |
Output is correct |
33 |
Correct |
335 ms |
12792 KB |
Output is correct |
34 |
Runtime error |
619 ms |
275456 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
35 |
Halted |
0 ms |
0 KB |
- |