leetcode2322 从树中删除边的最小分数

思路：

枚举+树的dfs序。参考了https://leetcode.cn/problems/minimum-score-after-removals-on-a-tree/solution/dfs-shi-jian-chuo-chu-li-shu-shang-wen-t-x1kk/。

实现：

 1 class Solution {
 2 public:
 3     int dfs(int x,int p,vector<int>&nums,vector<int>&sum,vector<int>&in,vector<int>&out,int&cnt,vectorint>>&g,vector<int>&par){
 4         par[x]=p;
 5         cnt++;
 6         in[x]=cnt;
 7         int res=nums[x];
 8         for(int i=0;i){
 9             int to=g[x][i];
10             if(to==p){
11                 continue;
12             }
13             int tmp=dfs(to,x,nums,sum,in,out,cnt,g,par);
14             res^=tmp;
15         }
16         sum[x]=res;
17         out[x]=cnt;
18         return res;
19     }
20     bool check(int x,int y,vector<int>&in,vector<int>&out){
21         if(x==y)return true;
22         return in[x]<in[y] and in[y]<=out[x];
23     }
24     int minimumScore(vector<int>& nums, vectorint>>& edges) {
25         int n=nums.size();
26         vectorint>>g(n,vector<int>());
27         for(int i=0;i){
28             int x=edges[i][0];
29             int y=edges[i][1];
30             g[x].push_back(y);
31             g[y].push_back(x);
32         }
33         vector<int>in(n,0),out(n,0),sum(n,0),par(n,-1);
34         int cnt=0;
35         dfs(0,-1,nums,sum,in,out,cnt,g,par);
36         int res=0x3f3f3f3f;
37         for(int i=0;i1;i++){
38             for(int j=0;j1;j++){
39                 if(i==j){
40                     continue;
41                 }
42                 int x1=edges[i][0],y1=edges[i][1];
43                 if(par[x1]==y1){
44                     swap(x1,y1);
45                 }
46                 int x2=edges[j][0],y2=edges[j][1];
47                 if(par[x2]==y2){
48                     swap(x2,y2);
49                 }
50                 int a=0,b=0,c=0;
51                 if(check(y1,x2,in,out)){
52                     a=sum[y2];
53                     b=sum[y1]^sum[y2];
54                     c=sum[0]^sum[y1];
55                 }
56                 else if(check(y2,x1,in,out)){
57                     a=sum[y1];
58                     b=sum[y1]^sum[y2];
59                     c=sum[0]^sum[y2];
60                 }
61                 else{
62                     a=sum[y1];
63                     b=sum[y2];
64                     c=sum[0]^sum[y1]^sum[y2];
65                 }
66                 int minn=min(a,min(b,c));
67                 int maxn=max(a,max(b,c));
68                 res=min(res,maxn-minn);
69             }
70         }
71         return res;
72     }
73 };