题解：AT_abc448_d [ABC448D] Integer-duplicated Path

tangtianyao0123 · 2026-03-07 23:09:28 · 题解

题目传送门。

不难发现，1\sim k 的路径是不受根节点的影响的，也就是说我们可以把这棵树以 1 为根，因为这样子是特别好计算的。

我们发现当 1\sim k 的路径中有两个重复的值会有两种情况：

第一种情况好处理，关键看第二种。

我们可以使用一个 multiset 维护。当遍历到这个节点时插入 a_k，遍历其儿子之后删除回溯。这样子就能保证在遍历到节点 k 时，有且仅有它的祖先在这个 multiset 中。

核心代码：

void dfs(int u, int fa){
  ans[u] = ans[fa] || s.count(a[u]);
  s.insert(a[u]);
  for(int v : g[u]){
    if(v == fa) continue;
    dfs(v, u);
  }
  s.erase(s.find(a[u]));//只能删掉一个
}