#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) (__builtin_popcountll(a))
#define bithigh(a) (63-__builtin_clzll(a))
#define lg bithigh
#define highpow(a) (1LL << (ll)lg(a))
using namespace std;
class Tree{
private:
int n, root;
vector<int> depth, in, out;
vector<vector<int> > g, par;
int _edges_ = 0;
bool _initialized_ = 0;
bool Valid(int s) const { return s >= 0 && s < n; }
int InitDfs(int s, int p = -1, int d = 0, int t = 0){
par[s][0] = p;
depth[s] = d;
in[s] = t;
for (int u : g[s])
if (u^p)
t = InitDfs(u, s, d+1, t+1);
return out[s] = ++t;
}
void Dfs(int s, int p, void bf(int, int), void af(int, int)) const {
bf(s, p);
for (int u : g[s])
if (u^p)
Dfs(u, s, bf, af);
af(s, p);
}
public:
Tree(int n = 0){ Assign(n); }
void Assign(int n = 0){
this->n = n;
depth.assign(n, 0);
in.assign(n, 0);
out.assign(n, 0);
g.assign(n, vector<int>());
par.assign(n, vector<int>(lg(n)+1, -1));
}
void Edge(int u, int v){
if (!Valid(u) || !Valid(v)){
cerr << "Node index out of range" << endl;
exit(1);
}
g[u].pb(v);
g[v].pb(u);
_edges_++;
}
void Read(int d = 1){
for (int i = 0; i < n-1; i++){
ri(u); ri(v);
u -= d; v -= d;
Edge(u, v);
}
}
void Initialize(int s = 0){
if (!Valid(s)){
cerr << "Node index out of range" << endl;
exit(1);
}
if (_edges_ < n-1){
cerr << "Tree is not connected" << endl;
exit(1);
}
if (_edges_ > n-1){
cerr << "Tree has cycle(s)" << endl;
exit(1);
}
root = s;
InitDfs(s);
for (int d = 1; d <= lg(n); d++)
for (int i = 0; i < n; i++)
if (depth[i] >= (1<<d))
par[i][d] = par[par[i][d-1]][d-1];
_initialized_ = 1;
}
int Size() const { return n; }
int Depth(int s) const {
if (!Valid(s)){
cerr << "Node index out of range" << endl;
exit(1);
}
return depth[s];
}
int InTime(int s) const {
if (!Valid(s)){
cerr << "Node index out of range" << endl;
exit(1);
}
return in[s];
}
int OutTime(int s) const {
if (!Valid(s)){
cerr << "Node index out of range" << endl;
exit(1);
}
return out[s];
}
vector<int> GetAdjecent(int s) const {
if (!Valid(s)){
cerr << "Node index out of range" << endl;
exit(1);
}
return g[s];
}
vector<int> GetChilds(int s) const {
if (!Valid(s)){
cerr << "Node index out of range" << endl;
exit(1);
}
vector<int> ch;
for (int u : g[s])
if (u^par[s][0])
ch.pb(u);
return ch;
}
int Par(int s, int d = 1) const {
if (!_initialized_){
cerr << "Tree has not been initialized yet" << endl;
exit(1);
}
if (d < 0 || d > depth[s]) return -1;
if (!d) return s;
return Par(par[s][lg(d)], d - highpow(d));
}
bool Ancestor(int s, int p) const {
if (!_initialized_){
cerr << "Tree has not been initialized yet" << endl;
exit(1);
}
return in[s] > in[p] && out[s] < out[p];
}
int Lca(int u, int v) const {
if (!Valid(u) || !Valid(v)){
cerr << "Node index out of range" << endl;
exit(1);
}
if (!_initialized_){
cerr << "Tree has not been initialized yet" << endl;
exit(1);
}
if (depth[u] > depth[v]) swap(u, v);
if (Ancestor(v, u)) return u;
v = Par(v, depth[v] - depth[u]);
for (int d = lg(n); ~d; d--){
if (par[u][d] != par[v][d]){
u = par[u][d];
v = par[v][d];
}
}
return par[u][0];
}
int Dist(int u, int v) const {
if (!Valid(u) || !Valid(v)){
cerr << "Node index out of range" << endl;
exit(1);
}
if (!_initialized_){
cerr << "Tree has not been initialized yet" << endl;
exit(1);
}
int lca = Lca(u, v);
return 2*depth[lca] - depth[u] - depth[v];
}
void Dfs(void bf(int, int), void af(int, int)) const { Dfs(root, -1, bf, af); }
};
#define Empty [](int, int){}
class dsu{
private:
int n;
vector<int> comp, sz;
vector<vector<int> > g;
void dfs(int s, int c){
if (this->comp[s] == c) return;
this->comp[s] = c;
for (int u : this->g[s])
dfs(u, c);
}
public:
void init(int n){
this->n = n;
this->sz = vector<int>(n, 1);
this->comp = vector<int>(n);
for (int i = 0; i < n; i++) this->comp[i] = i;
this->g = vector<vector<int> >(n);
}
void merge(int s, int u){
if (comp[s] == comp[u]) return;
this->g[s].pb(u);
this->g[u].pb(s);
if (this->sz[this->comp[s]] < this->sz[this->comp[u]]) swap(s, u);
this->sz[this->comp[s]] += this->sz[this->comp[u]];
this->sz[this->comp[u]] = 0;
dfs(u, this->comp[s]);
}
int find(int s) const { return this->comp[s]; }
int clean(){
int mp[this->n];
memset(mp, -1, sizeof(mp));
int m = 0;
for (int i = 0; i < this->n; i++)
if (this->sz[this->comp[i]])
if (!~mp[this->comp[i]])
mp[this->comp[i]] = m++;
for (int i = 0; i < n; i++)
this->comp[i] = mp[this->comp[i]];
return m;
}
};
const ll LINF = 4e18;
const int mxN = 1e6+10, INF = 2e9;
ll n, m, cnt, a[mxN], lca[mxN], sum[mxN];
ll leafs[mxN];
Tree tree, sub;
dsu ds;
void dfs(int s, int p){
for (int u : tree.GetChilds(s)) sum[s] += sum[u];
if (sum[s] && ~p) ds.merge(s, p);
}
void subdfs(int s, int p){
for (int u : sub.GetChilds(s)) leafs[s] += leafs[u];
if (!leafs[s]) leafs[s] = 1;
}
int CT(int s, int p){
for (int u : sub.GetChilds(s))
if (leafs[u] > leafs[0]/2) return CT(u, s);
return s;
}
void Solve(){
cin >> n >> m;
tree.Assign(n);
tree.Read();
tree.Initialize();
memset(lca, -1, sizeof(lca));
for (int i = 0; i < n; i++){
cin >> a[i]; a[i]--;
if (!~lca[a[i]]) lca[a[i]] = i;
else lca[a[i]] = tree.Lca(lca[a[i]], i);
}
for (int i = 0; i < n; i++){
sum[i]++; sum[lca[a[i]]]--;
}
ds.init(n);
tree.Dfs(Empty, &dfs);
sub.Assign(ds.clean());
for (int s = 0; s < n; s++)
for (int u : tree.GetChilds(s))
if (ds.find(s) != ds.find(u))
sub.Edge(ds.find(s), ds.find(u));
sub.Initialize();
sub.Dfs(Empty, &subdfs);
int ct = CT(0, -1);
sub.Initialize(ct);
memset(leafs, 0, sizeof(leafs));
sub.Dfs(Empty, &subdfs);
if (sub.Size() == 1) cout << 0 << en;
else if (sub.Size() < 4) cout << 1 << en;
else cout << (leafs[ct]+1)/2 << en;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0); cerr.tie(0);
cout << setprecision(12) << fixed;
cerr << setprecision(12) << fixed;
cerr << "Started!" << endl;
int t = 1;
//cin >> t;
while (t--)
Solve();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
16080 KB |
Output is correct |
| 2 |
Correct |
7 ms |
15956 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
15956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
16080 KB |
Output is correct |
| 2 |
Correct |
7 ms |
15956 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
15956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
16080 KB |
Output is correct |
| 2 |
Correct |
7 ms |
15956 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
15956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
107 ms |
41872 KB |
Output is correct |
| 2 |
Correct |
177 ms |
56316 KB |
Output is correct |
| 3 |
Correct |
13 ms |
16852 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
16596 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
16080 KB |
Output is correct |
| 2 |
Correct |
7 ms |
15956 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
15956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
