LeetCode 5848. 树上的操作（dfs序）

题意：

给你一棵 n 个节点的树，编号从 0 到 n - 1 ，以父节点数组 parent 的形式给出，
其中 parent[i] 是第 i 个节点的父节点。树的根节点为 0 号节点，所以 parent[0] = -1 ，
因为它没有父节点。你想要设计一个数据结构实现树里面对节点的加锁，解锁和升级操作。
数据结构需要支持如下函数：
Lock：指定用户给指定节点 上锁 ，上锁后其他用户将无法给同一节点上锁。
只有当节点处于未上锁的状态下，才能进行上锁操作。
Unlock：指定用户给指定节点 解锁 ，只有当指定节点当前正被指定用户锁住时，才能执行该解锁操作。
Upgrade：指定用户给指定节点 上锁 ，并且将该节点的所有子孙节点 解锁 。
只有如下 3 个条件 全部 满足时才能执行升级操作：
指定节点当前状态为未上锁。
指定节点至少有一个上锁状态的子孙节点（可以是 任意 用户上锁的）。
指定节点没有任何上锁的祖先节点。
请你实现 LockingTree 类：
LockingTree(int[] parent) 用父节点数组初始化数据结构。
lock(int num, int user) 如果 id 为 user 的用户可以给节点 num 上锁，那么返回 true ，
否则返回 false 。如果可以执行此操作，节点 num 会被 id 为 user 的用户 上锁 。
unlock(int num, int user) 如果 id 为 user 的用户可以给节点 num 解锁，那么返回 true ，
否则返回 false 。如果可以执行此操作，节点 num 变为 未上锁 状态。
upgrade(int num, int user) 如果 id 为 user 的用户可以给节点 num 升级，那么返回 true
，否则返回 false 。如果可以执行此操作，节点 num 会被 升级 。
数据范围：
n == parent.length
2 <= n <= 2000
对于 i != 0 ，满足 0 <= parent[i] <= n - 1
parent[0] == -1
0 <= num <= n - 1
1 <= user <= 1e4
parent 表示一棵合法的树。
lock ，unlock 和 upgrade 的调用 总共 不超过 2000 次。

解法：

首先发现数据不大,可以接受O(n^2)复杂度的算法.
用lc[i]记录节点i的上锁用户.
对于上锁和解锁操作,O(1)判断处理即可.
对于升级操作,暴力判断子孙节点和祖先结点是否满足条件即可,
如何快速找子孙节点和祖先节点?我用的是dfs序.

code：

const int maxm=2e3+5;
class LockingTree {
public:
vector<int>g[maxm];
int L[maxm],R[maxm],idx;
int rk[maxm];
int lc[maxm];
int n;
void dfs(int x){
L[x]=++idx;
rk[idx]=x;
for(int v:g[x]){
dfs(v);
}
R[x]=idx;
}
LockingTree(vector<int>& a) {
n=a.size();
for(int i=0;i<n;i++)g[i].clear();
for(int i=1;i<n;i++){
g[a[i]].push_back(i);
}
//预处理dfs序
idx=0;
dfs(0);
}
bool lock(int x, int user) {
if(!lc[x]){
lc[x]=user;
return 1;
}
return 0;
}
bool unlock(int x, int user) {
if(lc[x]==user){
lc[x]=0;
return 1;
}
return 0;
}
bool upgrade(int x, int user) {
if(!lc[x]){
//判断是否有子孙被锁住了
int ok1=0;
for(int i=L[x]+1;i<=R[x];i++){
if(lc[rk[i]])ok1=1;
}
//判断是否有祖先被锁住了
int ok2=1;
for(int i=0;i<n;i++){
if(i!=x&&L[i]<=L[x]&&R[i]>=R[x]&&lc[i])ok2=0;
}
if(ok1&&ok2){
lc[x]=user;
for(int i=L[x]+1;i<=R[x];i++){
lc[rk[i]]=0;
}
return 1;
}
return 0;
}
return 0;
}
};
/**
* Your LockingTree object will be instantiated and called as such:
* LockingTree* obj = new LockingTree(parent);
* bool param_1 = obj->lock(num,user);
* bool param_2 = obj->unlock(num,user);
* bool param_3 = obj->upgrade(num,user);
*/

最后

以上就是干净日记本为你收集整理的LeetCode 5848. 树上的操作（dfs序）的全部内容，希望文章能够帮你解决LeetCode 5848. 树上的操作（dfs序）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。