[BZOJ 1954] The xor-longest Path Trie树贪心

Description#

给定一棵n个点的带权树，求树上最长的异或和路径

Input#

The input contains several test cases. The first line of each test case contains an integer n(1<=n<=100000), The following n-1 lines each contains three integers u(0 <= u < n),v(0 <= v < n),w(0 <= w < 2^31), which means there is an edge between node u and v of length w.

Output#

For each test case output the xor-length of the xor-longest path.

Sample Input#

Sample Output#

1
7

题解#

本题是要求树上的路径异或只要先预处理出每个点到根的路径的异或值又因为异或两次会抵消所以结果一定是对的

然后将所有点的异或值都插入一块Trie二进制由高到低

枚举每一个点贪心的在Trie树中找就可以了

1
/*
2
 * @Author: WildRage
3
 * @Date: 2017-06-13 10:24:04
4
 * @Last Modified by:   WildRage
5
 * @Last Modified time: 2017-06-13 10:24:04
6
 */
7
#include<iostream>
8
#include<cstdio>
9
#include<cstring>
10
using namespace std;
11
struct Trie_Node{
12
    Trie_Node *ch[27];
13
    Trie_Node(){
14
        memset(ch,0,sizeof(ch));
15
    }
16
}*root;
17
int ans;
18
inline void insert(char *s){
19
    int len=strlen(s);
20
    Trie_Node *now=root;
21
    for(int i=0;i<len;i++){
22
        if(now->ch[s[i]-'A']==NULL)
23
            now->ch[s[i]-'A']=new Trie_Node,ans++;
24
        now=now->ch[s[i]-'A'];
25
    }
26
}
27
int main()
28
{
29
    freopen("trie.in","r",stdin);
30
    freopen("trie.out","w",stdout);
31
    char s[105];
32
    root=new Trie_Node;ans++;
33
    while(scanf("%s",s)!=EOF) insert(s);
34
    printf("%d",ans);
35
}