您现在的位置是:首页 >学无止境 >时间戳优化网站首页学无止境
时间戳优化
简介时间戳优化
题意
给定一颗有根树,起初点全为白色,序列 a [ i ] a[i] a[i]表示在第 i i i秒将 a [ i ] a[i] a[i]染成黑色,求在每次染色后有多少颗子树中既有黑色又有白色节点。
int n;
cin >> n;
vector<int> mn(n + 1), mx(n + 1);
vector<vector<int>> g(n + 1);
for(int i = 2, x; i <= n; i++) {
cin >> x;
g[x].pb(i);
}
for(int i = 1; i <= n; i++) {
int x;
cin >> x;
mn[x] = mx[x] = i;
}
function<void(int)> dfs = [&](int x) {
for(int y : g[x]) {
dfs(y);
mn[x] = min(mn[x], mn[y]);
mx[x] = max(mx[x], mx[y]);
}
};
dfs(1);
//编号为i的点的子树内在[mn[i], mx[i] - 1]的时间内为斑马子树
// for(int i = 1; i <= n; i++) DD(mn[i], mx[i]);
vector<int> sum(n + 1);
for(int i = 1; i <= n; i++) {
sum[mn[i]]++;
sum[mx[i]]--;
}
for(int i = 1; i <= n; i++) {
sum[i] += sum[i - 1];
cout << sum[i] << ' ';
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。