No.2980 Planar Tree 2
タグ : / 解いたユーザー数 39
作問者 :
tko919
/ テスター :
testestest
Problem Statement
You are given an undirected tree $T$ with $N$ vertices numbered from $1$ to $N$. The $i$-th edge connects vertex $u_i$ and vertex $v_i$.
For each vertex of $T$, place a point on the circumference of a circle independently and uniformly at random, then connect these points with line segments corresponding to the edges.
Find the probability, $\bmod\ 998244353$, that no line segment shares a point with another line segment except at their endpoints.
Formally, the problem is as follows.
For each vertex $v$, assign some $\theta_v \in [0,2\pi)$ independently and uniformly at random, and let $P_v=(\cos(\theta_v),\sin(\theta_v))$.
Then, for an edge $e=(u,v)$, let $I_e$ be the line segment connecting $P_u,P_v$ on the unit disk.
Find the probability, $\bmod\ 998244353$, that the following condition is satisfied.
- For any distinct edges $e,f$, the line segments $I_e,I_f$ do not intersect except at their endpoints.
What is a probability $\bmod\ 998244353$?
It can be proved that the required probability is always a rational number. Moreover, under the constraints of this problem, when the value is expressed as ${P \over Q}$ using $2$ coprime integers $P,Q$, it can be proved that there exists exactly one integer $R$ such that $R \times Q \equiv P( \bmod\ 998244353)$ and $0 \leq R < 998244353$. Find this $R$.Input
$N$
$u_1\ v_1$
$\vdots$
$u_{N-1}\ v_{N-1}$
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq u_i < v_i \leq N$
- The graph given in the input is a tree.
- All input values are integers.
Output
Print the answer, followed by a newline.
Sample
Sample 1
Input
4 1 2 2 3 3 4
Output
665496236
When the circle is divided by the chord corresponding to edge $1$, the segments do not intersect if and only if the points corresponding to vertices $3,4$ lie on the same side.
The required probability is $\int_0^1 x^2+(1-x)^2 dx={2 \over 3}$.
Sample 2
Input
10 1 7 7 10 8 10 3 8 4 8 9 10 6 9 5 9 2 7
Output
795030324
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。