Deletable Nodes in a Tree

ID: 14077

Type: Default

1000ms

256MiB

You are given a tree with $$n$$ nodes numbered from 1 to $$n$$. The tree has $$n-1$$ edges.

In addition, there are two sets of special node pairs given:

A set of good pairs: $$\{\langle u_1,v_1\rangle,\langle u_2,v_2\rangle,\dots,\langle u_a,v_a\rangle\}$$.
A bad pair: $$\langle b_u,b_v\rangle$$.

A node $ x $ (with $1\le x\le n$) is deletable if and only if after removing node $x$ (and all edges incident to it) the following conditions hold:

For every good pair $\langle u_i,v_i\rangle$ ($1\le i \le a$), the remaining two nodes are still connected in the tree. Note that if either $u_i$ or $v_i$ is deleted, they are considered disconnected.
The bad pair $\langle b_u,b_v\rangle$ becomes disconnected. (Similarly, if one of them is deleted, they are considered disconnected.)

In other words, a node $x$ can be deleted if and only if:

$x$ is not one of the endpoints of any good pair, and
For every good pair $\langle u,v \rangle$, $x$ does not lie on the unique simple path between $u$ and $v$ in the tree,
and for the bad pair $\langle b_u,b_v \rangle$, either $x$ is one of $b_u$ or $b_v$ or $x$ lies on the unique path between $b_u$ and $b_v$.

Your task is to count the number of nodes that can be deleted.

Hint: In a tree, given any two nodes $u$ and $v$, a node $x$ lies on the unique simple path between them if and only if
$$d(u,v) = d(u,x) + d(x,v),$$
where $d(x,y)$ denotes the distance between $x$ and $y$.

inputFormat

The first line contains two integers $$n$$ and $$a$$, representing the number of nodes and the number of good pairs respectively.

The next $$n-1$$ lines each contain two integers $u$ and $v$ indicating an edge between nodes $u$ and $v$ in the tree.

The following $$a$$ lines each contain two integers $u_i$ and $v_i$ representing a good pair.

The last line contains two integers $b_u$ and $b_v$ representing the bad pair.

outputFormat

Output a single integer: the number of nodes that can be deleted while satisfying the conditions.

sample

#P11967. Deletable Nodes in a Tree

Deletable Nodes in a Tree