题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

JAVA代码

//万能开头：
import java.util.Scanner;
import java.lang.Math;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.lang.Comparable;
import java.util.Collections;
import java.util.Map;
import java.util.HashMap;
import java.util.NavigableMap;
import java.util.TreeMap;
import java.util.PriorityQueue;
import java.util.Queue;
class Main{
static class Trie{
int val = 2;
Trie left; // 0
Trie right; // 1
public Trie(int v){
val = v;
}
}

//建立Trie
static void insert(int srcVal){
    Trie node = root;
    for(int i=30; i>=0; i--){
        int xorVal = (srcVal >> i) & 1;
        if(xorVal == 0){
            if(node.left == null){
                node.left = new Trie(0);
            }
            node = node.left;
        }else if(xorVal == 1){
            if(node.right == null){
                node.right = new Trie(1);
            }
            node = node.right;
        }
    }
}
/**
 * 返回异或后的值
 * */
 static int queryXorAndRes(int val){
    int ans = 0;
    Trie node = root;
    for(int i=30; i>=0; i--){
        int xorVal = (val >> i) & 1;
        if(xorVal == 1){ //走左节点
            if(node.left != null){ //相反位存在
                ans += 1<<i;
                node = node.left;
            }else if(node.right != null){
                node = node.right;
            }else break;   
        }else if(xorVal == 0){//走右分支
            if(node.right != null){ //相反位存在
                ans += 1<<i;
                node = node.right;
            }else if(node.left != null){
                node = node.left;
            }else{
                break;
            }
        }
    }
    return ans; 
}
static Scanner sc = new Scanner(System.in);
static Trie root = new Trie(2);
static int[]h;
static int[]e;
static int[]w;
static int[]ne;
static int cnt;
static int[]a;
static void init(int n){
    h = new int[n];
    for(int i=0;i<n;i++)h[i] =-1;
    e  = new int[n * 2];
    w  = new int[n * 2];
    ne = new int[n * 2];
    a  = new int[n];
}
static void addEdge(int u,int v, int weight){
    e[cnt] = v;
    w[cnt] = weight;
    ne[cnt] = h[u];
    h[u] = cnt++;
}
//数组模拟邻接表，无向图的经典dfs 遍历
static void dfs(int u, int father ,int sum){
    a[u] = sum;
    for(int i=h[u]; i>-1; i = ne[i]){
        int v = e[i];
        if(v == father) continue;
        dfs(v,u,sum ^ w[i]);
    }
}

public static void main(String []args){
    int num = sc.nextInt();
    init(num);
    for(int i=1;i<num;i++){
        int u = sc.nextInt();
        int v = sc.nextInt();
        int w = sc.nextInt();
        addEdge(u,v,w);
        addEdge(v,u,w);
    }
    // 生成每一个点到root路径的异或值
    dfs(0,-1,0);

    for(int i=0; i<num; i++)insert(a[i]);
    int res = 0;
    for(int i=0; i<num; i++){
        res = Math.max(res, queryXorAndRes(a[i])); 
    }
    System.out.println(res);
}

}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla