Educational Codeforces Round #105 A-Z Graph - 图论 + 构造

题意

有$n$个点，$m$次操作。操作有三种：

1. + u v c。建立u到v的有向边，边上的字母为c。保证不会重边。
2. - u v。删除u到v的有向边。保证有边可删。
3. ? k。问你是否存在这样的k个点，使v1->v2->v3->...->vk的边构成的字符串和vk->vk-1->vk-2->...->v1的边构成的字符串相同。（点可以重复）

题解

点可以重复那就很显然了。

假设有解，那么必然存在v1->v2和v2->v1两条边。

如果k是奇数，那我们可以不假思索的得出这样的路线：v1->v2->v1->v2->v1。其返回的路线也是v1->v2->v1->v2->v1。那不管v1->v2和v2->v1的字母是啥，只要k是奇数，就一定是一样的。

如果k是偶数就稍微麻烦一点点。以k=4为例，假设有解，解为：v1->v2->v3->v4。其反过来是v4->v3->v2->v1。且这两个的字符串相同。
于是我们可以发现v2->v3和v3->v2的字母一定是一样的。那就很简单了。
我们其实可以构造v2->v3->v2->v3，其反面是v3->v2->v3->v2。

综上，对于k是奇数，我们找能直接互联的两个点。如果k是偶数，找能直接互联且字母一样的两个点。

代码