logic Trees

بعد از گذراندن درس‌های مدار‌ منطقی و طراحی الگوریتم در ترم گذشته، پالرمو (دقت کنید که این اسم باشگاه یا مکان نیست، اسم یک فرد واقعی است!)‎ به فکر ارائه‌ی یک نوع درخت جدید، با نام ‎«درخت منطقی‎» افتاد. در‌خت منطقی یک درخت وزن‌دار است که بر روی هر یال آن علاوه بر یک عدد طبیعی، یکی از سه عملگر ‎$\{and‎, ‎or‎, ‎xor\}$‎ نیز نوشته شده است. برای هر یال ‎$uv$‎‌ در این درخت ‎$w_{uv}$‎ نمایان‌گر وزن آن یال و ‎$\text{op}_{uv} \in \{and‎, ‎or‎, ‎xor\}$‎ نمایان‌گر عملگر روی آن یال می‌باشد.

به ازای رأس‌های ‎$a$‎ و ‎$b$‎ و عدد طبیعی ‎$x$‎ بر روی این درخت، ‎$f(a,b,x)$‎ به صورت زیر تعریف می‌شود:

• اگر ‎$a = b$‎ باشد: $f(a,b,x) = x‎$
• اگر ‎$a \ne b$‎ باشد، و ‎$c$‎‌ راس قبل از ‎$b$‎ روی مسیر از ‎$a$‎ به ‎$b$‎ باشد: $f(a,b,x) = \text{op}_{bc}(f(a,c,x),w_{bc})$ که در آن منظور از ‎$\text{op}(z,t)$‎ انجام عملیات ‎$op$‎‌ بر روی ‎$z$‎‌ و ‎$t$‎ می‌باشد. بعنوان مثال $and(2,3)=2$ (عملگر‌های تعریف شده در این سوال عملگر‌های بیتی می‌باشند).

با ‎«انتشار»‎ عدد ‎$x$‎ از روی راس ‎$a$‎ به کل درخت، ارزش هر راس ‎$b$‎ به اندازه ‎$f(a,b,x)$‎ افزایش می‌یابد. حال پالرمو که این ترم دستیار آموزشی درس گراف‌های منطقی است، از دانشجویان خواسته تا برنامه‌ای بنویسند که یک درخت منطقی و تعدادی دستور انتشار را به عنوان ورودی گرفته و ارزش راس‌های درخت را بعد از انجام تمامی انتشار‌ها محاسبه‌ کند. ارزش تمامی راس‌های درخت در ابتدا برابر با صفر است. حال وظیفه‌ی شما نوشتن برنامه‌ای برای پاسخ به این سوال چالشی آقای پالرمو است.

• در سطر اول ورودی به ترتیب دو عدد طبیعی ‎$n$‎، تعداد راس‌های درخت و ‎$q$‎، تعداد دستور‌های انتشار آمده است.
• ‎$n-1$‎ سطر بعدی هر یک شامل سه عدد طبیعی ‎$u$‎، ‎$v$‎ و ‎$w$‎ و یک عملگر ‎$op$‎ از مجموعه‌ی ‎$\{and‎, ‎or‎, ‎xor\}$‎ هستند. به این معنی که یالی میان راس‌های ‎$u$‎ و ‎$v$‎ با وزن ‎$w$‎ و عملگر ‎$op$‎ وجود دارد‎.‎
• سپس، ‎$q$‎ سطر بعدی هر کدام شامل دو عدد طبیعی ‎$a$‎ و ‎$x$‎ است به این معنی که عدد ‎$x$‎‌ از راس ‎$a$‎ انتشار پیدا می‌کند.
• $1 \leq n \leq 10^5$‎
• $1 \leq q \leq 3\times10^5$‎
• $1 \leq u,v,a \leq n$‎
• $1 \leq w,x \leq 10^9$‎
• $op \in \{and‎, ‎or‎, ‎xor\}$

در تنها سطر خروجی ارزش راس‌های ‎$1$‎ تا ‎$n$‎‌ را بعد از انجام انتشار‌ها چاپ کنید.

• زیرمسئله‌ی اول (۲۰ نمره): در همه‌ی تست‌ها ‎$n\leq 1000$‎.
• زیرمسئله‌ی دوم (۱۰ نمره): در همه‌ی تست‌ها عملگر ‎$op$‎ تنها از مجموعه ‎$\{and‎, ‎or\}$‎ است.
• زیرمسئله‌ی سوم (۱۰ نمره): در همه‌ی تست‌ها عملگر ‎$op$‎ تنها از مجموعه ‎$\{xor\}$‎ است.
• زیرمسئله‌ی چهارم (۶۰ نمره): در همه‌ی تست‌ها ‎$n\leq 10^5$‎.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل