[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

4

1 2 3

2 3 4

2 4 6

Sample Output

7

题解

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

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

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

/*
 * @Author: WildRage 
 * @Date: 2017-06-13 10:24:04 
 * @Last Modified by:   WildRage 
 * @Last Modified time: 2017-06-13 10:24:04 
 */
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct Trie_Node{
    Trie_Node *ch[27];
    Trie_Node(){
        memset(ch,0,sizeof(ch));
    }
}*root;
int ans;
inline void insert(char *s){
    int len=strlen(s);
    Trie_Node *now=root;
    for(int i=0;i<len;i++){
        if(now->ch[s[i]-'A']==NULL)
            now->ch[s[i]-'A']=new Trie_Node,ans++;
        now=now->ch[s[i]-'A'];
    }
}
int main()
{
    freopen("trie.in","r",stdin);
    freopen("trie.out","w",stdout);
    char s[105];
    root=new Trie_Node;ans++;
    while(scanf("%s",s)!=EOF) insert(s);
    printf("%d",ans);
}
本文作者 : NekoMio
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
本文链接 : https://www.nekomio.com/2017/06/13/3/
上一篇
下一篇