محدودیت زمان: ۲ ثانیه محدودیت حافظه: ۲۵۶ مگابایت منبع: آزمون نهایی اول دوره ۲۶ المپیاد…
- User
محدودیت زمان: ۲ ثانیه محدودیت حافظه: ۲۵۶ مگابایت منبع: آزمون نهایی اول دوره ۲۶ المپیاد کامپیوتر امین برای تعطیلات به پوستون رفته است. یکی از جاذبههای گردشگری پوستون میدانهای بزرگ و زیبای آن هستند. میدانهای شهر با تعدادی خیابان به یکدیگر متصل شدهاند.
امین برای جابهجایی بین میدانها در شهر میتواند از اوبر یا اسنپ تاکسی بگیرد! هر کدام از این دو شرکت مجموعهای از خیابانهای شهر را تحت پوشش قرار داده است، به طوری که با خیابانهای تحت پوشش هر کدام از شرکتها به تنهایی، میتوان با یک مسیر یکتا از هر میدانی به هر میدان دیگر رفت. همچنین، هیچ خیابانی وجود ندارد که تحت پوشش هر دو شرکت اوبر و اسنپ باشد.
امین میخواهد بین میدانهای شهر دور دور کند. او عملیات دور دور را به این شکل انجام میدهد که از یک میدان دلخواه شروع میکند، از هیچ خیابانی بیش از یک بار عبور نمیکند و در نهایت به میدان نخست بر میگردد. او در هر حرکت یک بار از یکی از دو شرکت تاکسی میگیرد و با این کار از یک سر یک خیابان که تحت پوشش آن شرکت است به سر دیگر آن خیابان میرود.
به دلیل این که هزینهی استفاده از تاکسیهای اوبر بسیار زیاد است، امین حداکثر دوبار میتواند از آنها استفاده کند، اما به هر تعداد دلخواهی میتواند از تاکسیهای اسنپ استفاده کند. از طرفی تاکسیهای اوبر به مراتب لوکستر از تاکسیهای اسنپ هستند و در نتیجه در نظر دارد که حتماً از دو مرتبهای که میتواند هزینهی تاکسیهای اوبر را پرداخت کند استفاده کند. پس یک دور دور از نظر امین به صرفه است اگر و تنها اگر در طول آن دقیقاً دوبار از تاکسیهای اوبر استفاده شود.
امین دو دور دور را در صورتی متفاوت در نظر میگیرد که در یکی از آنها از خیابانی عبور کنیم که در دور دور دیگر از آن عبور نخواهیم کرد. آیا میتوانید با گرفتن مسیرهای تحت پوشش اوبر و مسیرهای تحت پوشش اسنپ، تعداد دور دورهای مختلف که امین میتواند انجام دهد را بشمارید؟
ورودی در خط اول ورودی عدد n n، تعداد میدانهای پوستون، آمده است. در n − 1 n−1 خط بعدی، در هر خط دو عدد طبیعی v s , i v s,i و u s , i u s,i آمده است که نشان میدهد خیابان متصل کنندهی آن دو میدان تحت پوشش اسنپ است. در n − 1 n−1 خط بعدی، در هر خط دو عدد طبیعی v u , i v u,i و u u , i u u,i آمده است که نشان میدهد خیابان متصل کنندهی آن دو میدان تحت پوشش اوبر است. بین هر دو میدان حداکثر یک خیابان وجود دارد. با تاکسیهای تحت پوشش هر شرکت میتوان از هر میدان به هر میدان دیگر رسید.
4 ≤ n ≤ 100
000 4≤n≤100 000 1 ≤ v s , i , u s , i ≤ n 1≤v s,i ,u s,i ≤n 1 ≤ v u , i , u u , i ≤ n 1≤v u,i ,u u,i ≤n
خروجی در تنها خط خروجی، تعداد دور دورهای به صرفه در پوستون را چاپ کنید.
زیرمسئلهها زیرمسئله نمره محدودیت ۱ ۲۰ n ≤ 100 n≤100 ۲ ۲۲ n ≤ 3
000 n≤3 000 ۳ ۵۸ بدون محدودیت اضافی مثال ورودی نمونه ۱ 4 1 2 2 3 3 4 1 3 1 4 2 4 Plain text خروجی نمونه ۱ 3 Plain text ورودی نمونه ۲ 7 1 2 1 3 2 4 2 5 3 6
3 7 1 4 4 5 1 7 7 6 6 2 2 3 Plain text خروجی نمونه ۲ 12 c++ - Assistant
To solve this problem, we need to determine the number of unique "profitable" cycles in the city of Polostan. A cycle is considered profitable if it includes exactly two Uber edges. Let's break down the approach to solve this problem effectively.
Step-by-Step Solution:
-
Understanding the Problem:
- Trees Definition: We are given two trees, Snapp (S) and Uber (U), both being spanning trees for
nnodes. Each tree hasn-1edges, and these edges are distinct. - Cycle Formation: A cycle is formed by selecting two edges from U and combining them with appropriate edges from S.
- Counting Unique Cycles: We need to count all possible unique pairs of U edges, each pair forming a unique cycle when combined with S edges.
- Trees Definition: We are given two trees, Snapp (S) and Uber (U), both being spanning trees for
-
Key Observations:
- Disjointness: Since S and U trees are edge-disjoint, taking any two different U edges and combining them with S edges will always form a unique cycle.
- Distinct Cycles: Each unique pair of U edges will result in a distinct cycle. There is no need to worry about overlapping paths because the trees ensure unique connectivity without shared edges.
-
Solution Approach:
- Combinatorial Counting: The number of ways to choose 2 U edges out of
m_u(wherem_u = n-1) is given by the combination formulaC(m_u, 2) = m_u * (m_u - 1) / 2. - Final Answer: The number of possible profitable cycles is simply the number of unique pairs of U edges.
- Combinatorial Counting: The number of ways to choose 2 U edges out of
-
Implementation:
- Read the input values.
- Count the number of U edges.
- Calculate the combination
C(m_u, 2).
Conclusion:
Given that each pair of U edges forms a unique cycle, the total number of profitable cycles is simply the number of ways to choose 2 U edges from the available U edges. This is a straightforward combinatorial problem, and we can directly compute the result using the combination formula.
Here's the implementation in C++:
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(false); cin.tie(0); ll n; cin >> n; // Skip n-1 Snapp edges for(int i=0;i<n-1;i++){ ll u, v; cin >> u >> v; } // Read U edges ll m_u = n-1; // No action needed as we only need m_u // As per problem, assuming all pairs can form cycles // Thus, answer is C(m_u,2) ll answer = (m_u)*(m_u -1)/2; cout << answer; } -