$\Large\texttt{P5838}$

$\small\texttt{In My cnblog}$

前言

这道题似乎是我遇到的第一道用 $\texttt{tarjan}$ 求 $\texttt{LCA}$ 思想的题目，感谢一楼题解神仙的点拨

不会$\texttt{tarjan}$ 求 $\texttt{LCA}$ 的可以参考我的博客（也没啥必要）

题意

给你一棵树，每个点有点权，每次询问节点 $n$ 到节点 $m$ 的路径上是否有点权为 $p$ 的点。

$n,m \le 10^5$

思路

以下$[n,m]$均表示为 $n$ 到 $m$ 的路径

观察 $n$ 到 $m$ 的路径，若路径上有点权为 $p$ 的点（我们只要找到一个这样的点，所以就假设这个点只有一个），那么可能在 $[\texttt{LCA}(n,m),n]$ 上，也可能在 $[\texttt{LCA}(n,m),m]$ 上。

如何记录这个点？

记录每个询问在 $[\texttt{LCA}(n,m),n]$ 上或许有些困难，我们发现其实维护 $DFS$ 访问到 $n$ 时 $[1,n]$ 上很好维护，如何利用起来？

可以发现一个性质，若有一个点权为 $p$ 的点在 $[1,n]$ 上，且它是点权为 $p$ 的在这路径上最深的，若它不在 $[\texttt{LCA}(n,m),n]$ 上，则没有点权为 $p$ 的在 $[\texttt{LCA}(n,m),n]$ 上~~(好像又是废话)~~。

并且，若这个权值为 $p$ 的节点不在 $[\texttt{LCA}(n,m),n]$ 上，也不在 $[\texttt{LCA}(n,m),m]$ 上，则 $[1,n]$ 和 $[1,m]$ 上的最深权值为 $p$ 的节点是相同的， 若不同，则答案为TRUE

因此：遍历到节点 $n$ ，只需记录 $[1,n]$ 上，每种 $C_i$ 的最深点

发现这两条性质，就可以愉快做题了，因为$\forall C_i\le10^5$ ，完全可以给开一个桶（不用离散化），遍历到每一个节点 $n$ 时，维护好这个桶，遍历到点 $n$ 时，将关于 $n$ 的所有询问遍历一遍（先离线询问），若询问第一次遍历到，标记次询问，即 $[1,n]$ 上深度最低、点权为 $p$ 的节点，遍历到点 $m$ 时，比较标记的点与是否 $[1,m]$ 上中深度最低、点权为 $p$ 的节点是否相同，不同则代表必定有一条路径上有要找的点权 $p$ 的节点（注意特判这个点为 $\texttt{LCA}(n,m)$ ）。

为了特判 $\texttt{LCA}(n,m)$，可以在桶里面标记点权为 $p$ 的节点为它在 $[1,n]$ 这条链上儿子。

注意特判询问 $n$ 和 $m$ 相等时 。

有时候看似很显然的性质，却有令人意想不到的思路。

时间复杂度 $\texttt{O(N + 2M)}$ 。

不管是码量还是效率，都远超大部分题解。

代码

#include <bits/stdc++.h>
using namespace std;

#define PB push_back
const int N = 1e5;
inline char nc()
{
        static char buf[1000000], *p1 = buf, *p2 = buf;
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
#define getchar nc
inline int read()
{
        int s = 0;
        register bool neg = 0;
        register char c = getchar();
        for (; c < '0' || c > '9'; c = getchar())
                neg |= (c == '-');
        for (; c >= '0' && c <= '9'; s = s * 10 + (c ^ 48), c = getchar())
                ;
        s = (neg ? -s : s);
        return s;
}

int a, b, s[N + 10], p[N + 10], ans[N + 10], top[N + 10];
vector<int> st[N + 10], ask[N + 10];

inline void dfs(int n, int fa)
{
        int pp = top[s[n]];
        for (int i = 0; i < ask[n].size(); i++)
        {
                int x = ask[n][i];
                if (ans[x] == -1)
                        ans[x] = top[p[x]];
                else
                        ans[x] = (top[p[x]] != ans[x]);
        }
        for (int i = 0; i < st[n].size(); i++)
        {
                int v = st[n][i];
                if (v == fa)
                        continue;
                top[s[n]] = v;
                dfs(v, n);
        }
        top[s[n]] = pp;
}

signed main()
{
        memset(ans, -1, sizeof(ans));
        a = read();
        b = read();
        for (int i = 1; i <= a; i++)
                s[i] = read();
        int x, y, z;
        for (int i = 1; i < a; i++)
        {
                x = read();
                y = read();
                st[x].PB(y);
                st[y].PB(x);
        }
        for (int i = 1; i <= b; i++)
        {
                x = read();
                y = read();
                p[i] = read();
                if (s[x] == p[i] || s[y] == p[i])
                        ans[i] = 1;
                ask[x].PB(i);
                ask[y].PB(i);
        }
        dfs(1, 0);
        for (int i = 1; i <= b; i++)
                printf("%d", ans[i]);
        return 0;
}