Az S. 108. feladat (2016. május)

S. 108. András és Béla egy fa-gráfon játszik, melynek \(\displaystyle N\) (\(\displaystyle 1\le N\le 100\,000\)) csúcsa van. Összesen \(\displaystyle M\) (\(\displaystyle 1\le M\le 100\,000\)) lépésből áll a játék. Minden lépés kétféle lehet:

- András kiválasztja a fa két csúcsát, és a köztük lévő egyértelmű út minden élére egy csokit helyez.

- Béla megkérdezi, hogy egy adott élen hány csoki van.

A feladat: Béla kérdéseit gyorsan megválaszolni.

A program olvassa be a standard input első sorából \(\displaystyle N\)-et és \(\displaystyle M\)-et, majd a következő \(\displaystyle N-1\) sorból a fa éleit: \(\displaystyle u\), \(\displaystyle v\) egészeket. Ezután \(\displaystyle M\) sor következik. Minden sor egy P vagy Q betűvel kezdődik, majd egy \(\displaystyle u, v\) egész számpár következik. Ez utóbbi számpár egy csúcspárt jelöl. A ,,P'' betű jelentése, hogy András az \(\displaystyle (u, v)\) csúcsok közti egyértelmű út minden élére tesz egy csokit. A ,,Q'' betű jelentése, hogy Béla megkérdezi, hogy hány csoki van az \(\displaystyle (u, v)\) élen. A program írja a standard output soraiba a Béla kérdéseire adott válaszokat.

Pontozás és korlátok: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani az 1 mp futásidőkorláton belül.

Beküldendő egy tömörített s108.zip állományban a program forráskódja, valamint a program rövid dokumentációja, amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2016. június 10-én LEJÁRT.

Statisztika:

8 dolgozat érkezett.
10 pontot kapott:	Gáspár Attila.
9 pontot kapott:	Janzer Orsolya Lili, Németh 123 Balázs, Noszály Áron.
8 pontot kapott:	2 versenyző.
3 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.

A KöMaL 2016. májusi informatika feladatai