T134561 「SWTR-05」Switch

小 A 有 $n$ 个开关，由 $n-1$ 根电线连接形成了一棵树。**一开始，每个开关都是关闭的。** 每个开关由 $m$ 个按钮所控制。**一开始，所有按钮都亮着红灯。** 当按下一个开关的第 $i$ 个按钮： - 如果这个开关的第 $i$ 个按钮原来亮红灯，那么它会亮绿灯。该开关启动。 - 如果这个开关的第 $i$ 个按钮原来亮绿灯，那么它会亮红灯。该开关关闭。 小 A 进行了 $q$ 次操作，格式为 $\texttt{x y s}$：表示按下开关 $x,y$ 间路径上所有开关的第 $s$ 个按钮。 由于操作实在太多，小 A 想知道进行这些操作之后开关打开与关闭的情况。

第一行，三个整数 $n,m,q$。 接下来 $n-1$ 行，每行两个整数 $x,y$，表示开关 $x,y$ 间有一条电线。 接下来 $q$ 行，每行三个整数 $x,y,s$，表示按下开关 $x,y$ 间路径上所有开关的第 $s$ 个按钮。

输出一个长度为 $n$ 的 $\texttt{01}$ 字符串。如果第 $i$ 个开关最终处于打开状态，第 $i$ 个字符应为 $\texttt{1}$，否则为 $\texttt{0}$。

「样例 $1$ 说明」  第 $1$ 次操作：按下路径 $1\to 3$ 上所有开关的第 $1$ 个按钮，操作结束后的开关状态：`1110`。 第 $2$ 次操作：按下路径 $4\to 3$ 上所有开关的第 $2$ 个按钮，操作结束后的开关状态：`1111`。 第 $3$ 次操作：按下路径 $2\to 4$ 上所有开关的第 $1$ 个按钮，操作结束后的开关状态：`1011`。 「数据范围与约定」 **本题采用捆绑测试。** - Subtask 1（9 points）：$n=1$。 - Subtask 2（21 points）：$n,m,q\leq 2\times 10^3$。 - Subtask 3（17 points）：$m=1$。 - Subtask 4（23 points）：树的形态是一条链。 - Subtask 5（30 points）：无特殊限制。 对于 $100\%$ 的数据：$1\leq n,q\leq 10^5$，$1\leq m\leq 10^9$。 对于每条电线：$1\leq x,y\leq n$，$x\neq y$。保证形成的是一颗树。 对于所有操作：$1\leq x,y\leq n$，$1\leq s\leq m$。 **本题轻微卡常，请注意常数优化。** --- 「题目来源」 [Sweet Round 05](https://www.luogu.com.cn/contest/28195) C。 idea & solution：[ET2006](https://www.luogu.com.cn/user/115194)。