Description

給定一棵帶邊權(quán)的樹, 選擇兩條沒有公共邊的簡單路徑 (長度可以為 0 ),使得所有在任意一條路徑上的邊的異或和盡量大。

Solution

題目要求選擇的兩條路徑不能有公共邊，但是考慮若兩條路徑有公共邊，公共部分就會被異或掉，所以這個條件就不需要考慮了。
然后O(n2)預(yù)處理所有路徑的值，丟到一個01Trie中求最大值就行了。

Code

#include<bits/stdc++.h>using namespace std;typedef long long ll; typedef pair<int, int> PII; typedef vector<int> VI; #define For(i , j , k) for (register int i = (j) , i##_end_ = (k) ; i <= i##_end_ ; ++ i) #define Fordown(i , j , k) for (register int i = (j) , i##_end_ = (k) ; i >= i##_end_ ; -- i) #define Set(a , b) memset(a , b , sizeof(a)) #define pb(a) push_back(a) #define mp(a, b) make_pair(a, b) #define ALL(a) (a).begin(), (a).end() #define SZ(a) ((int)(a).size()) #define fir first #define sec second #define INF (0x3f3f3f3f) #define INF1 (2139062143) #define Mod (1000000007) #ifdef hany01 #define debug(...) fprintf(stderr , __VA_ARGS__) #else #define debug(...) #endiftemplate <typename T> inline bool chkmax(T &a , T b) { return a < b ? (a = b , 1) : 0; } template <typename T> inline bool chkmin(T &a , T b) { return b < a ? (a = b , 1) : 0; }int _ , __; char c_; inline int read() {for (_ = 0 , __ = 1 , c_ = getchar() ; !isdigit(c_) ; c_ = getchar()) if (c_ == '-') __ = -1;for ( ; isdigit(c_) ; c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);return _ * __; }inline void File() {freopen("a.in" , "r" , stdin);freopen("a.out" , "w" , stdout); }const int maxn = 2003;int n, fa[maxn], tmp, v[maxn], w[maxn], nex[maxn], beg[maxn], e, cnt, Max, lc[2096], rc[2096], rt;inline void add(int uu, int vv, int ww) { v[++ e] = vv; w[e] = ww; nex[e] = beg[uu]; beg[uu] = e; }inline void insert(int x) {int t = 0;Fordown(i, 9, 0){if (x & (1 << i)) if (rc[t]) t = rc[t]; else t = rc[t] = ++ cnt;else if (lc[t]) t = lc[t]; else t = lc[t] = ++ cnt;} }void dfs(int u, int dis, int fa) {for (int i = beg[u]; i; i = nex[i]){if (v[i] == fa) continue;insert(dis ^ w[i]);dfs(v[i], dis ^ w[i], u);} }inline bool chkin(int x) {int t = 0;Fordown(i, 9, 0) if (x & (1 << i)) if (rc[t]) t = rc[t]; else return false;else if (lc[t]) t = lc[t]; else return false;return true; }inline void check(int x) {int t = 0, Ans = 0;Fordown(i, 9, 0){if (x & (1 << i)) if (lc[t]) t = lc[t], Ans |= (1 << i); else t = rc[t];else if (rc[t]) t = rc[t], Ans |= (1 << i); else t = lc[t];}chkmax(Max, Ans); }inline void answer() {For(i, 0, 1023) if (chkin(i)) check(i); }void debugg(int u, int now) {if (!lc[u] && !rc[u]){printf("%d\n", now);return ;}if (lc[u]) debugg(lc[u], now << 1);if (rc[u]) debugg(rc[u], now << 1 | 1); }int main() {File();n = read();For(i, 2, n) fa[i] = read() + 1;int tmp;For(i, 2, n) tmp = read(), add(fa[i], i, tmp), add(i, fa[i], tmp);insert(0);for (rt = 1; rt <= n; ++ rt) dfs(rt, 0, 0);answer();printf("%d\n", Max);return 0; } //今夜鄜州月,閨中只獨看。 //遙憐小兒女，未解憶長安。 //香霧云鬟濕，清輝玉臂寒。 //何時倚虛幌，雙照淚痕干！ //--杜甫《月夜》

總結(jié)

以上是生活随笔為你收集整理的SRM 719 div2 Hard (01Trie,最大异或和)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。