2096: [USACO 2026 First Contest, Gold] Problem 1. COW Traversals
题目描述
There are () cows labeled on Farmer John's farm, where each cow lives in its own barn. Each cow has a best friend (). Cows can be best friends with themselves, and multiple cows can have the same best friend. The cows love to party, so they have decided to throw a party for () consecutive nights.
On night , cow will decide to throw a party of type at its barn, where . This party will exist for all future nights as well, until cow decides to throw a party of a different type.
Every night, each cow will attempt to go to a party. If a cow is not hosting a party, they will check their best friend's barn, and if there is no party there, will follow their best friend to wherever they are going (who might also follow their best friend and so on). It is possible that a cow might never find a party and will then give up for the night.
Compute for each night, the number of cows that end up at a party of type , , and respectively.
输入
The second line contains , where is cow 's best friend.
The third line contains , the number of nights.
The next lines each contain an integer () and a character , representing the cow that is throwing the party and the party type respectively.
输出
样例输入
5
2 3 4 5 4
4
2 C
4 C
4 W
2 O样例输出
2 0 0
5 0 0
2 0 3
0 2 3提示
On night , there is only one party of type at barn , which only cows and attend.
On night , there is a new party of type at barn , which cows , , and can now reach.
On night , the party at barn is changed to type , affecting cows , and .
On night , the party at barn is changed to type , affecting cows and .
SCORING:
- Input 2:
- Inputs 3-4:
- Inputs 5-9: is a permutation of
- Inputs 10-21: No additional constraints