Codeforces 1467E Distinctive Roots in a Tree
题目链接
题意
给定一个大小为 \(n\) \((1 \le n \le 2 \times 10^5)\) 的树，每个点有一个权值 \(a_i\) \((1 \le a_i \le 10^9)\)，求有多少个点 \(u\) 满足从 \(u\) 出发的任意一条路径上的点权值不重复
思路
对于两个权值相同的点，容易发现其两端之外的点一定都是不满足条件的点。
我们可以进行一个树的遍历，可以发现两个权值相同的点 \(u, v\) 的位置有两种，一种是\(u\) 是 \(v\) 的祖先，另一种是 \(u,v\) 没有祖先关系
- 如果 \(u\) 是 \(v\) 的祖先，那么 \(v\) 的子树 以及以 \(u\) 的其它子节点为根的子树里面的点都是不满足条件的，我们可以在 \(dfs\) 序上实现用区间加标记一下整个区间。将 \(1-dfn[u]\) 以及 \(dfn[out[v] + 1] - n\) 的区间都加一，表示这部分是不合法的点
- 如果 \(u, v\) 没有祖先关系，那么说明 \(v\) 不在以 \(u\) 为根的子树中，那么我们可以直接将 \(u\) 的子树标记即可
点击查看代码
/********************
Author: Nanfeng1997
Contest: Luogu
URL: https://www.luogu.com.cn/problem/CF1467E
When: 2022-03-26 12:51:31
Memory: 250MB
Time: 3000ms
********************/
#include
#define _ 0
using namespace std;
using LL = long long;
struct splitmix64 {
size_t operator()(size_t x) const {
static const size_t fixed = chrono::steady_clock::now().time_since_epoch().count();
x += 0x9e3779b97f4a7c15 + fixed;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
};
void solve() {
int n; cin >> n;
vector w(n), d(n + 1), dfn(n), out(n);
unordered_map mp, cnt;
for(int &x: w) {
cin >> x;
mp[x] ++;
}
vector > son(n);
for(int i = 1; i < n; i ++ ) {
int u, v; cin >> u >> v;
u --, v --;
son[u].push_back(v);
son[v].push_back(u);
}
int ans = 0, ck = 0;
function dfs = [&] (int u, int fa) {
dfn[u] = ++ ck;
int pre = cnt[w[u]];
cnt[w[u]] ++;
for(int &v: son[u]) {
if(v == fa) continue;
int now = cnt[w[u]];
dfs(v, u);
if(cnt[w[u]] > now) {
d[1] ++, d[dfn[v]] --;
d[out[v] + 1] ++;
}
}
out[u] = ck;
if(cnt[w[u]] - pre < mp[w[u]]) {
d[dfn[u]] ++, d[out[u] + 1] --;
}
};
dfs(0, -1);
for(int i = 1; i <= n; i ++ ) {
d[i] += d[i - 1];
if(!d[i]) ans ++;
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1; //cin >> T;
while(T --) solve();
return ~~(0 ^ _ ^ 0);
}