首页 > ACM题库 > HDU-杭电 > HDU 4776-Ants-DFS-[解题报告]HOJ
2015
09-17

HDU 4776-Ants-DFS-[解题报告]HOJ

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

http://www.csdn123.com/html/itweb/20131111/216497.htm

题意:给一棵边权树,一直蚂蚁从一个节点爬到另一个节点获得的分数是路径上的所有边异或和。m 个询问,求第k大。(u-v和v-u是算两个值)

(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

记录当前节点已经是rank第几大了,下一步就是要求 rank 的下一个。这个只要用 Trie 树记录一下自己有多少个孩子就能 log(1e18) 的时间复杂度内求出来。即——
假设当前位置的二进制是 0 ,那么最大的肯定是 走 1 那条边。
1、如果 1 的子树中节点个数 >= rank ,那么走下去
2、如果小于 rank ,那么 rank -= 节点个数,走 0;
3、如果没有 1 的子树,那么走 0;
如果是 0 则同理。
2.次大值:

Solution Of BNU lsy 

就是你在某个节点的时候
然后比方说发现当前位选1比较大
然后回溯前选的就是1
并且这个位置可以选0
就往0那边走
否则回溯
以下是用的求第k值的处理方法:

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;
};
Edge adj[maxn << 1];
int tot;
int head[maxn];
void init_adj()
{
    tot = 0;
    CLR(head, -1);
}
void add_edge(int x, int y, LL v)
{
    adj[tot].to = y;
    adj[tot].v = v;
    adj[tot].next = head[x];
    head[x] = tot++;
}

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;
    for (int r = head[u]; r != -1; r = adj[r].next)
    {
        int v = adj[r].to;
        if (v == fa) continue;
        dfs(v, u, val ^ adj[r].v);
    }
}

void solve()
{
    int x, y;
    LL vv;
    init_adj();
    REP(i, n - 1)
    {
        scanf("%d%d%I64d", &x, &y, &vv);
        add_edge(x, y, vv);
        add_edge(y, x, 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;
}

参考:http://blog.csdn.net/guognib/article/details/15707293