换根dfs - wenzhoullq/leetcode GitHub Wiki
换根首先分类别,如果只有一条路径或则对跟所有的节点有关,则不断更新ans[0];如果是一个树里找出一个路径,则需要维护 up,down1,down2,p三个数组
核心思想:
两次dfs,最后时间复杂度为O(2n)
第一次dfs,并且第一次dfs是后序遍历
第二次dfs,是对ans[son] = ans[cur] + 相关,并且第二次dfs是先序遍历(只会对son进行更新
int[] ans;
int n;
List<Integer>[] list;
public int[] huangen(int n, int[][] edges) {
this.list = new List[n];
this.ans = new int[n];
this.n = n;
Arrays.setAll(list,e->new LinkedList<>());
for(int[] edge:edges){
int y = edge[0],x= edge[1];
list[y].add(x);
list[x].add(y);
}
dfs(-1,0,0);
reroot(-1,0);
return ans;
}
void dfs(int fa,int cur,int deep){
ans[0]+=deep;
for(int son:list[cur]){
if(son == fa) continue;
dfs(cur,son,deep+1);//后续遍历
}
}
void reroot(int fa, int cur){
for(int son:list[cur]){
if(son == fa) continue;
ans[son] = ans[cur] + 相关数据;
reroot(cur,son);
}
}
- 题目
int n ;
int[] up,down1,down2,p;
List<Integer>[] list;
public List<Integer> huangen(int n, int[][] edges) {
this.n = n;
this.up = new int[n];
this.down1 = new int[n];
this.down2 = new int[n];
this.p = new int[n];
list = new List[n];
Arrays.setAll(list,e->new LinkedList<>());
for(int[] edge:edges){
int y = edge[0], x = edge[1];
list[y].add(x);
list[x].add(y);
}
dfs(-1,0);
reroot(-1,0);
return ans;
}
int dfs(int fa,int cur){
for(int son:list[cur]){
if(son==fa) continue;
int f = dfs(cur,son) + ;//具体根据题目
if(f >= down1[cur]){
down2[cur] = down1[cur];
down1[cur] = f;
p[cur] = son;
}else if( f > down2[cur]){
down2[cur] = f;
}
}
return down1[cur];
}
void reroot(int fa,int cur){
for(int son:list[cur]){
if(son==fa) continue;
if(son==p[cur]){
up[son] = Math.max(up[son],down2[cur] + );//具体根据题目
}else{
up[son] = Math.max(up[son],down1[cur] + );//具体根据题目
}
up[son] = Math.max(up[son],up[cur]+ );//具体根据题目
reroot(cur,son);
}
}
- 题目
2538. 最大价值和与最小价值和的差值(树形DP做比较快