题解 P5838 【USACO19DEC】Milk Visits G

· · 题解

\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;
}