2015
09-17

# Ants

There are some apple trees in a farm. An apple tree can be described as a connected graph which has n nodes and n-1 edges. The apples are the nodes and the branches are the edges. Every edge is assigned a value denoting the length of the branch.
Now in the farm come a lot of ants, which are going to enjoy the delicious apples. The ants climb the tree one by one. Every ant would choose a node as the starting node and another node as the ending node, then it would crawl alone the unique path from the starting node to the ending node. The distance between two nodes is defined as the XOR sum of lengths of all the edges in the unique path between them. Every ant wants to crawl along such a path which the distance is as large as possible. But two ants cannot crawl from the same starting node to the same ending node. You should calculate the distance which the k-th ant crawled.
Note that the starting node and the ending node cannot be the same for an ant.

The input consists of several test case.
For each test case, the first line contain an integer n denoting the number of nodes.
The next n-1 lines each contains three integers x,y,z, denoting that there exists an edge between node x and node y and its length is z. The nodes are numbered from 1 to n.
The next line contain a integer m denoting the number of queries.
In the next m lines, each line contains an integer k denoting that you need to calculate the distance of the k-th ant.
The input ends with n = 0.
(1 <= n, m <= 100000, 1 <= x, y <= n, 0 <= z <= 1018, 1 <= k <= 200000)

The input consists of several test case.
For each test case, the first line contain an integer n denoting the number of nodes.
The next n-1 lines each contains three integers x,y,z, denoting that there exists an edge between node x and node y and its length is z. The nodes are numbered from 1 to n.
The next line contain a integer m denoting the number of queries.
In the next m lines, each line contains an integer k denoting that you need to calculate the distance of the k-th ant.
The input ends with n = 0.
(1 <= n, m <= 100000, 1 <= x, y <= n, 0 <= z <= 1018, 1 <= k <= 200000)

3
1 2 2
3 2 3
3
1
2
5
5
1 3 7
2 1 3
4 3 6
5 3 1
3
1
8
1000
0

3
3
1
7
6
-1
Hint
In the first test case, the first ant may crawl from node 2 to node 3, and the second ant may crawl from node 3 to node 2, and the 5-th ant may crawl from node 1 to node 3.
The distance of the 5-th ant can be calculated by 2 xor 3 = 1.


2013杭州现场赛 Ants

http://blog.csdn.net/dslovemz/article/details/15290899

（1）预处理出每个节点u到根节点的边权异或值a[u]，则两个节点u, v之间路径上的边权值的异或值为a[u]^a[v]

（2）将每个a[u]以二进制的形式插入到trie中

（3）u-v和v-u是算两个值。每个点u对应和其它的n-1个节点共有n-1个值，而共有n个节点，则可将所有的异或值，分成n类，每类n-1个。用优先队列，包含每类的当前最大值。初始为每个节点u和其它所有n-1个节点的值得最大值。取最大值后，删除后添加相应类别数列中的次大值。

（4）则关键求点u和其它n-1个点异或的第k大值即可，或者是求当前值得次大值

1.第k值法：

## Solution Of Dshawn by cxlove

1、如果 1 的子树中节点个数 >= rank ，那么走下去
2、如果小于 rank ，那么 rank -= 节点个数，走 0；
3、如果没有 1 的子树，那么走 0；

2.次大值：

## Solution Of BNU lsy

ps:hdu提交用lld wa， 用i64d才ac

#pragma comment(linker, "/STACK:102400000000,102400000000")
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <string>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;

//LOOP
#define FF(i, a, b) for(int i = (a); i < (b); ++i)
#define FD(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define FE(i, a, b) for(int i = (a); i <= (b); ++i)
#define FED(i, b, a) for(int i = (b); i>= (a); --i)
#define REP(i, N) for(int i = 0; i < (N); ++i)
#define CLR(A,value) memset(A,value,sizeof(A))
//INPUT
#define RI(n) scanf("%d", &n)
#define RII(n, m) scanf("%d%d", &n, &m)
#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)
#define RS(s) scanf("%s", s)
typedef long long LL;
typedef unsigned long long ULL;
typedef vector <int> VI;
const int INF = 0x3f3f3f3f;
const double eps = 1e-10;
const int maxn = 100010;

LL a[maxn];
LL ans[200010];
LL BIT[62];
int n, m;
struct Trie{
int ch[2 * maxn * 62][2];
LL val[2 * maxn * 62];
int num[2 * maxn * 62];
int tol;
Trie(){}
void init()
{
tol = 1;
CLR(ch, 0);
CLR(val, 0);///
CLR(num, 0);
}
void insert(LL x)
{
int u = 0;
for (int i = 60; i >= 0; i--)
{
int v = (x & BIT[i]) > 0;///
if (!ch[u][v]) ch[u][v] = tol++;
u = ch[u][v];
num[u]++;
}
val[u] = x;
}
bool kth_max(int k, LL v, LL &vmax)///查找和v异或后值为第k大值
{
if (k >= n) return 0;
int u = 0;
for (int i = 60; i >= 0; i--)
{
int r = !((v & BIT[i]) > 0);///
if (ch[u][r])
{
if (num[ch[u][r]] >= k)
u = ch[u][r];
else
{
k -= num[ch[u][r]];
u = ch[u][r ^ 1];///
}
}
else
u = ch[u][r ^ 1];///
}
vmax = val[u] ^ v;
return 1;
}
}ac;

struct Edge{
int to, next;
LL v;
};
int tot;
{
tot = 0;
}
void add_edge(int x, int y, LL v)
{
}

struct query{
int k, id;
bool operator <(const query &b) const
{
return k < b.k;
}
}qy[200010];

struct Node{
int k;
LL v;
LL vmax;
bool operator <(const Node &b) const
{
return vmax < b.vmax;
}
};
priority_queue<Node>q;

void dfs(int u, int fa, LL val)
{
ac.insert(val);///!!!
a[u] = val;
{
if (v == fa) continue;
}
}

void solve()
{
int x, y;
LL vv;
REP(i, n - 1)
{
scanf("%d%d%I64d", &x, &y, &vv);
}
RI(m);
REP(i, m)
{
RI(qy[i].k);
qy[i].id = i;
}
sort(qy, qy + m);

ac.init();
dfs(1, -1, 0);

while (!q.empty()) q.pop();
FE(i, 1, n)
{
Node now;
now.k = 1;
now.v = a[i];
if (ac.kth_max(now.k, now.v, now.vmax)) q.push(now);
}
int rank  = 1;///
REP(i, m)
{
while (!q.empty() && rank < qy[i].k)
{
rank++;
Node now = q.top(); q.pop();
now.k++;
if (ac.kth_max(now.k, now.v, now.vmax)) q.push(now);
}
if (!q.empty()) ans[qy[i].id] = q.top().vmax;
else ans[qy[i].id] = -1;
}
REP(i, m)
printf("%I64d\n", ans[i]);
}

int main()
{
for (int i = 0; i <= 60; i++) BIT[i] = 1ll << i;
while (~RI(n) && n)
solve();
return 0;
}


1. 没看过，不过大街上卖内衣的广告，路边性事用品店应该都屏蔽下吧。最主要的是超市里居然收银处摆的都是避孕套。怎么也没人管管，哪个孩子不去超市啊，被当糖果买回去怎么给孩子交代

2. 你说是保家卫国，金家三代也是这样想的，他们觉得他们不欠中国的，而且还替中国守住东大门，吃你的喝你的是应该的，中国人觉得当年的血白流了，他们却觉得现在该叫你中修了。