暴力部分:

　　这个题一开始的想法是 n^2 枚举两个点，然后logn维护LCA，在倍增的同时维护异或值和 k 的个数。

　　s_z_l老爷指导了新的思路，既然这个树只有n^2个LCA，那么枚举LCA，同时向下深搜即可。

 

标算:

　　首先点分治，尽力保证树的平衡，然后按照Trie树的性质，贪心，至于k，我们可以把每个节点的值置为like值的最大值，然后在走左右儿子的时候判断一下即可。

　　点分治时 !vis[E[i].v] && E[i].v != fa 一定不要忘

1 #include 
      
         2 #define rep(i, a, b) for (int i = a; i <= b; i++)  3 #define REP(i, a, b) for (int i = a; i < b; i++)  4 #define drep(i, a, b) for (int i = a; i >= b; i--)  5 #define travel(x) for (int i = G[x]; i; i = E[i].nx)   6 #define mp make_pair  7 #define pb push_back  8 #define clr(x) memset(x, 0, sizeof(x))  9 #define xx first 10 #define yy second 11 using namespace std; 12 typedef long long i64; 13 typedef pair
       
         pii; 14 //******************************** 15 const int maxn = 100005; 16 struct Ed { 17     int u, v, nx; Ed() {} 18     Ed(int _u, int _v, int _nx) : 19         u(_u), v(_v), nx(_nx) {} 20 } E[maxn << 1]; 21 int G[maxn], cnt_e; 22 void addedge(int u, int v) { 23     E[++cnt_e] = Ed(u, v, G[u]); 24     G[u] = cnt_e; 25 } 26 int vis[maxn]; 27 pii sta[maxn]; int top; 28 int rt; 29 int f[maxn], size[maxn], sum; 30 void getrt(int x, int fa) 31 { 32     f[x] = 0, size[x] = 1; 33     travel(x) { 34         if (!vis[E[i].v] && E[i].v != fa) { 35             getrt(E[i].v, x); 36             size[x] += size[E[i].v]; 37             f[x] = max(f[x], size[E[i].v]); 38         } 39     } 40     f[x] = max(f[x], sum - size[x]); 41     if (f[x] < f[rt]) rt = x; 42 } 43 int read() { 44     int l = 1, s(0); char ch = getchar(); 45     while (ch < '0' || ch > '9') { if (ch == '-') l = -1; ch = getchar(); } 46     while (ch >= '0'&& ch <= '9') { s = (s << 1) + (s << 3) + ch - '0'; ch = getchar(); } 47     return l * s; 48 } 49 int trie[3000005][2], tab[3000005], rootr; 50 int ntot; 51 int n, K; 52 int c[maxn], w[maxn]; 53 int query(int co, int k) { 54     int ret(0); 55     int p = rootr; 56     if (tab[p] + k < K) return -1; 57     drep(i, 30, 0) { 58         int id = co >> i & 1; 59         if (trie[p][id ^ 1] && tab[trie[p][id ^ 1]] + k >= K) ret |= 1 << i, p = trie[p][id ^ 1]; 60         else if (!trie[p][id] || tab[trie[p][id]] + k < K) { ret = -1; break; } 61         else p = trie[p][id]; 62     } 63     return ret; 64 } 65 void insrt(int co, int k) { 66     int p = rootr; 67     drep(i, 30, 0) { 68         tab[p] = max(tab[p], k); 69         int id = co >> i & 1; 70         if (!trie[p][id]) trie[p][id] = ++ntot; 71         p = trie[p][id]; 72     } 73     tab[p] = max(tab[p], k); 74 } 75 int ans = -1; 76 void dfs_query(int x, int fa, int co, int k) { 77     sta[++top] = mp(co, k); 78     ans = max(ans, query(co, k)); 79     for (int i = G[x]; i; i = E[i].nx) if (!vis[E[i].v] && E[i].v != fa) 80         dfs_query(E[i].v, x, co ^ w[E[i].v], k + c[E[i].v]); 81 } 82 /* 83    void dfs_insrt(int x, int fa, int co, int k) { 84    insrt(rootr, co, k, 30); 85    for (int i = G[x]; i; i = E[i].nx) if (!vis[E[i].v] && E[i].v != fa) 86    dfs_insrt(E[i].v, x, co ^ w[E[i].v], k + c[E[i].v]); 87    } 88  */ 89 void solve(int x) { 90     vis[x] = 1; 91     rep(i, 0, ntot) trie[i][0] = trie[i][1] = 0, tab[i] = 0; 92     rootr = 0; 93     ntot = 0; 94     if (c[x] >= K) ans = max(ans, w[x]); 95     insrt(w[x], c[x]); 96     travel(x) { 97         if (vis[E[i].v]) continue; 98         top = 0; 99         dfs_query(E[i].v, x, w[E[i].v], c[E[i].v]);100         rep(j, 1, top) {101             sta[j].xx ^= w[x], sta[j].yy += c[x];102             insrt(sta[j].xx, sta[j].yy);103         }104     }105     int tmp = sum;106     for (int i = G[x]; i; i = E[i].nx) {107         if (!vis[E[i].v]) {108             rt = 0; sum = size[E[i].v] > size[x] ? tmp - size[x] : size[E[i].v];109             getrt(E[i].v, 0);110             solve(rt);111         }112     }113 }114 int main() {115     n = read(), K = read();116     rep(i, 1, n) c[i] = read();117     rep(i, 1, n) w[i] = read();118     REP(i, 1, n) {119         int x, y; x = read(), y = read();120         addedge(x, y), addedge(y, x);121     }122     rt = 0, sum = n, f[0] = n + 1;123     getrt(1, 0);124     solve(rt);125     printf("%d\n", ans);126     return 0;127 }