首页 > ACM题库 > HDU-杭电 > HDU 4601-Letter Tree-线段树-[解题报告]HOJ
2015
09-17

HDU 4601-Letter Tree-线段树-[解题报告]HOJ

Letter Tree

问题描述 :

A letter tree is a rooted tree that each edge is assigned to a lowercase letter. Node 1 is always considered the root. When making a tour in the tree, one is only allowed to step "down". In other word, if you’re now on some node of the tree, you can only make a step to one of its children nodes.
After you travel along a path in the tree, you will obtain a Path String, which is formed by the letters assigned to edges that you just move along. The string exactly records all edges in the order of your visit.
Now we’re faced with the problem. Located at some node u on the tree, your task is to move for exactly m steps and obtain a maximal lexicographic Path String. In order to avoid the huge output, you’re only required to output the hash code of the string after it is transformed into a 26-base number, where ‘a’ for 0, ‘b’ for 1, …, ‘z’ for 25. For instance, "bac" = (678)26 for 678=1×262+0×261+2×260.

输入:

The input contains several test cases.
An integer T(T≤20) will exist in the first line of input, indicating the number of test cases.
Each test case begins with an integer N(2≤N≤105), which denotes the number of nodes in the tree.
The following (N-1) lines describe the edges. An edge is described in the format of (u,v,c), which denotes an undirected edge between u and v with a lowercase letter c assigned.
The following line contains a single integer M(1≤M≤105), indicating the number of queries.
The following M lines, each with a pair of positive integers (u,m), describe the queries. (1≤m≤105)
The nodes are labeled from 1 to N.

输出:

The input contains several test cases.
An integer T(T≤20) will exist in the first line of input, indicating the number of test cases.
Each test case begins with an integer N(2≤N≤105), which denotes the number of nodes in the tree.
The following (N-1) lines describe the edges. An edge is described in the format of (u,v,c), which denotes an undirected edge between u and v with a lowercase letter c assigned.
The following line contains a single integer M(1≤M≤105), indicating the number of queries.
The following M lines, each with a pair of positive integers (u,m), describe the queries. (1≤m≤105)
The nodes are labeled from 1 to N.

样例输入:

1
6
1 2 a
1 3 b
2 4 c
2 5 b
2 6 c
3
1 1
1 2
3 1

样例输出:

1
2
IMPOSSIBLE
Hint
The answer to the first two queries are respectively "b" and "ac". Note that "ac" and "c" have the same code under the 26-base transformation.

转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents    by—cxlove

题目:给出一棵树,1为根,边为字母,问从某个结点,向下走m步,路径形成一个字符串,要求字典序最大。

http://acm.hdu.edu.cn/showproblem.php?pid=4601

做法:直接做根本没法。。。每个结点孩子结点边上的字母可能相等。直接贪心都没法。m也很大。

我们如果知道从根到每个结点路径形成的字符串,

那么固定u,m,查询的话,终点必定是在同一层,depth[u] + m。从根到这个结点的字符串长度是一样的,而且必定存在LCP >= depth[u]。所以我们可以直接比较从根到终点的路径的字符串,而且对于每次查询,终点是在同一层。

我们就可以萌生离线做法,对于终点在同一层的查询一并处理。

那么我们需要求出根到每个结点的字典序排名,以及HASH值。

然后对于这样树型转线性的应该 不陌生,利用DFS的时间戳。

然后 对于每一层,可以用RMQ或者线段树查询最值。注意最值是字典序,不要用HASH值的大小。

接下来的问题是怎么得到字典序,原因在于原来的树每个结点的孩子中有相同的字母,那么我们就重构Trie。

大概就可以解决了:

step 1:构造Trie,避免边上字母一样的情况,作一些合并,原来的结点映射到Trie上的结点。

step 2:遍历Trie,给原来的结点标上rank值。

step 3:遍历原来的树,得到时间戳。

step 4:将查询分类之后,处理每一层,将同一层的值放到RMQ或者线段树中。

step 5:每个查询,二分得到对应区间,区间查询。

注意 :数据中有m = 0 的情况,坑啊。。。。。。。。。。。。。。。输出0

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define lson step << 1
#define rson step << 1 | 1
#pragma comment(linker,"/STACK:100000000,100000000")
using namespace std;
typedef long long LL;
const int N = 200005;
const LL MOD = 1000000007LL;
const LL HASH = 26LL;
struct Edge {
    int v , next , ch ;
}e[N << 1];
struct Trie {
    Trie *next[26];
    vector <int> v;
    void init () {
        v.clear();
        memset (next , 0 , sizeof(next));
    }
}s[N];
struct Question {
    int u , d , id;
    void input (int _i) {
        scanf ("%d %d" , &u , &d);
        id = _i;
    }
}question[N];
struct Seg_tree {
    int left , right;
    int maxrank;
    LL hash;
}L[N << 2];
vector<Question>askondep[N];
int n , start[N] , tot , idx;
LL hash[N] , fac[N] = {1};
int ans[N];
void _add (int u , int v , int c) {
    e[tot].v = v;
    e[tot].ch = c;
    e[tot].next = start[u];
    start[u] = tot ++;
}
void add (int u , int v , int c) {
    _add (u , v , c);
    _add (v , u , c);
}
Trie *NewNode () {
    Trie *t = &s[idx ++];
    t->init();
    return t;
}
void bulidtrie (Trie *p , int u , int pre , LL h) {
    p -> v.push_back (u);
    hash[u] = h;
    for (int i = start[u] ; i != -1 ; i = e[i].next) {
        int v = e[i].v , ch = e[i].ch;
        if (v == pre) continue;
        if (p -> next[ch] == NULL) p -> next[ch] = NewNode ();
        bulidtrie (p -> next[ch] , v , u , (h * HASH + ch) % MOD);
    }
}
int nowrank , rank[N];
void getrank (Trie *p ) {
    for (int i = 0 ; i < p -> v.size() ; i ++) {
        rank[p -> v[i]] = nowrank;
    }
    for (int i = 0 ; i < 26 ; i ++) {
        if (p -> next[i] != NULL) {
            nowrank ++;
            getrank (p -> next[i]);
        }
    }
}
vector<int> ondepth[N];
int depth[N] , id[N] , left_id[N] , right_id[N] , id_cnt , maxdep , mapping[N];
void caldepth (int u , int pre , int dep) {
    depth[u] = dep;
    id[u] = ++id_cnt;
    mapping[id_cnt] = u;
    left_id[u] = id_cnt + 1;
    ondepth[dep].push_back (id_cnt);
    maxdep = max (maxdep , dep);
    for (int i = start[u] ; i != -1 ; i = e[i].next) {
        int v = e[i].v;
        if (v == pre) continue;
        caldepth (v , u , dep + 1);
    }
    right_id[u] = id_cnt;
}
void push_up (int step) {
    if (L[lson].maxrank > L[rson].maxrank) {
        L[step].maxrank = L[lson].maxrank;
        L[step].hash = L[lson].hash;
    }
    else {
        L[step].maxrank = L[rson].maxrank;
        L[step].hash = L[rson].hash;
    }
}
void bulid (int step , int l , int r , int d) {
    L[step].left = l;
    L[step].right = r;
    if (l == r) {
        L[step].maxrank = rank[mapping[ondepth[d][l]]];
        L[step].hash = hash[mapping[ondepth[d][l]]];
        return ;
    }
    int m = (l + r) >> 1;
    bulid (lson , l , m , d);
    bulid (rson , m + 1 , r , d);
    push_up (step);
}
pair<int , LL> query (int step , int l , int r) {
    if (l < L[step].left || r > L[step].right || l > r) return make_pair(-1 , -1);
    if (L[step].left == l && L[step].right == r) {
        return make_pair (L[step].maxrank , L[step].hash);
    }
    int m = (L[step].left + L[step].right) >> 1;
    if (r <= m) return query (lson , l , r);
    else if (l > m) return query (rson , l , r);
    else {
        pair<int , int> u = query (lson , l , m);
        pair<int , int> v = query (rson , m + 1 , r);
        if (u.first > v.first) return u;
        return  v;
    }
}
int main () {
    #ifndef ONLINE_JUDGE
        freopen ("input.txt" , "r" , stdin);
        freopen ("output.txt" , "w" , stdout);
    #endif
    for (int i = 1 ; i < N ; i ++)
        fac[i] = (fac[i - 1] * 26LL) % MOD;
    int t , out = 0;
    scanf ("%d" , &t);
    while (t --) {
        tot = 0;idx = 0;
        memset (start , -1 , sizeof(start));
        scanf ("%d" , &n);
        for (int i = 1 ; i < n ; i ++) {
            int u , v ; char str[5];
            scanf ("%d %d %s" , &u , &v , str);
            add (u , v , str[0] - 'a');
        }
        Trie *root = NewNode ();
        bulidtrie (root , 1 , -1 , 0LL);
        nowrank = 0;
        getrank (root);
        id_cnt = 0;maxdep = 1;
        caldepth (1 , -1 , 1);
        int q;
        scanf ("%d" , &q);
        for (int i = 0 ; i < q ; i ++) {
            question[i].input(i);
            if (question[i].d == 0) ans[i] = 0;
            else if (depth[question[i].u] + question[i].d <= maxdep)
                askondep[depth[question[i].u] + question[i].d].push_back (question[i]);
            else  ans[i] = -1;
        }
        for (int dep = 1 ; dep <= maxdep ; dep ++) {
            if (askondep[dep].size () == 0) continue;
            int m = ondepth[dep].size() - 1;
            bulid (1 , 0 , m , dep);
            for (int i = 0 ; i < askondep[dep].size() ; i ++) {
                int u = askondep[dep][i].u , d = askondep[dep][i].d , id = askondep[dep][i].id;
                int l = left_id[u] , r = right_id[u];
                l = lower_bound (ondepth[dep].begin () , ondepth[dep].end () , l) - ondepth[dep].begin ();
                r = upper_bound (ondepth[dep].begin () , ondepth[dep].end () , r) - ondepth[dep].begin () - 1;   
                pair<int , LL> ret = query (1 , l , r);
                if (ret.second == -1) ans[id] = -1;
                else ans[id] = ((ret.second - (LL)hash[u] * fac[d]) % MOD + MOD) % MOD;
            }
        }
        for (int i = 0 ; i < q ; i ++) {
            if (ans[i] == -1) puts ("IMPOSSIBLE");
            else printf("%d\n" , ans[i]);
        }
        for (int i = 1 ; i <= maxdep ; i ++) {
            ondepth[i].clear();
            askondep[i].clear();
        }
    }
    return 0;
}


版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm_cxlove/article/details/9971567