hdu - 4601 - Letter Tree

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4601

 

——>>搞了整整2天。。。

 

这道题，我觉得非常不错。。。涉及乘法越界，bfs，dfs，trip，二分，RMQ（或者线段树），是目前做过的最综合的一道题目了（这也就意味着：我好水。。。）

 

对于询问（u, m），设最佳终点为des，这就说明从u开始，一直走到与des同深度的结点时，走des这条路径的字典序是最大的之一（可能有多个最大，但其哈希值一样），同时也说明，从根结点1走到这些结点（u的子结点中与des同深度的结点）时，走des这条路径的字典序是最大的之一（前面有公共前缀至少到u），于是可以利用根到各结点的字典序的排序来进行RMQ查询。先以树的深度为层次得到各个层次的dep[i]（每一层中按dfs到达的先后排序），对于每一个询问，求出其最佳终点所在的深度，这时u结点在这个深度的子孙必然是dep[i]中连续的一部分。是哪一部分呢？到达u的子孙的dfs_clock一定比到达u的大，也就比到达u的上一个兄弟在同一深度的子结点的dfs_clock大，那么二分找u，可得“这部分”的左端点，另一方面，u的子结点中dfs最后到达的那个结点，其dfs_clock一定 >= 到达最佳终点的，再一次二分就可得到“这部分”的右端点。接着就可以RMQ了。。。

 

注意：

 

1.求Hash不能放在dfs(v[e])后，因为dfs(v[e])要求已知Hash[v[e]]；

 

2.同一层次中push_back新结点时，这一操作应放在dfs(v[e])后，因为push_back是头插入的。

 

另外：虽然题目未说明输入树边时一定是从父结点到子结点的顺序，但实际证明这题是可以这样认为的。

 

#include <cstdio>  
#include <cstring>  
#include <queue>  
#include <vector>  
#include <algorithm>  
  
using namespace std;  
  
const int maxn = 100000 + 10;  
const int maxm = 200000 + 10;  
const int mod = 1000000000 + 7;  
  
int T, N, M;  
int head[maxn], nxt[maxm], v[maxm], w[maxm], ecnt;  
int fa[maxn];       //u = fa[v]表示u是v的父结点  
int pow26[maxn];        //pow26[i]表示26的i次方（对mod取模）  
int height[maxn];        //height[i]表示结点i的高（深）度，从1开始  
int maxHeight;      //最大深度  
int dfs_clock;      //dfs时间戳  
int in[maxn];       //in[i]表示第一次时间戳到结点i时的计数值  
int maxChild[maxn];      //maxChild[i]表示以结点i为根的子树中dfs最后到达的结点  
int Hash[maxn];     //Hash[i]表示从根结点1到结点i的哈希值  
int tail[maxn];     //tail[i]表示结点i到叶子的最长距离  
int ch[maxn][26];       //trip树结点  
int x2trip[maxn];       //x2trip[i]表示原结点i在trip中的编号  
int tripRank[maxn];     //在trip中各结点的名次（按字典序从小到大排）  
int Rank[maxn];     //Rank[x]表示原结点x的字典序名次  
int depBefore[maxn];        //depBefore[i]表示树的第i层共有多少个结点  
int a[maxn];        //a[i]表示结点按深度层次（同层按dfs到达的顺序）排好后第i个数对应的原结点号  
int d[maxn][20];      //d[i][j]表示从a[]中第i个数开始的连续2^j个数中Rank最大的原结点编号  
vector<int> dep[maxn];      //dep[i]表示深度为i的结点的集合（按dfs先后顺序排列）  
  
void init(){        //初始化  
    memset(head, -1, sizeof(head));  
    ecnt = dfs_clock = 0;  
    maxHeight = 1;  
}  
  
void addEdge(int uu, int vv, int ww){       //邻接表加边  
    v[ecnt] = vv;  
    w[ecnt] = ww;  
    nxt[ecnt] = head[uu];  
    head[uu] = ecnt;  
    ecnt++;  
}  
  
void getPow26(){        //得到26的次方数组  
    pow26[0] = 1;  
    for(int i = 1; i < maxn; i++) pow26[i] = (long long)pow26[i-1] * 26 % mod;  
}  
  
void bfs(){  
    queue<int> qu;  
    height[1] = 1;       //根结点的高度设为1  
    memset(ch, 0, sizeof(ch));      //初始化所有trip结点  
    int sz = 1;     //trip目前结点个数  
    x2trip[1] = 0;      //原根结点1对应trip根结点0  
    qu.push(1);  
    while(!qu.empty()){  
        int x = qu.front(); qu.pop();  
        int u = x2trip[x];      //取原结点x在trip中的对应编号  
        for(int e = head[x]; e != -1; e = nxt[e]){  
            if(!ch[u][w[e]]) ch[u][w[e]] = sz++;     //新增结点  
            x2trip[v[e]] = ch[u][w[e]];      //更新映射  
            height[v[e]] = height[x] + 1;     //求各结点的高度  
            maxHeight = max(maxHeight, height[v[e]]);  
            qu.push(v[e]);  
        }  
    }  
}  
  
void getTripRank(int x){        //获取trip中各结点的字典序名次  
    tripRank[x] = ++dfs_clock;  
    for(int c = 0; c < 26; c++) if(ch[x][c]) getTripRank(ch[x][c]);  
}  
  
void init2(){  
    for(int i = 1; i <= maxHeight; i++) dep[i].clear();     //初始化dep[]  
    dfs_clock = 0;      //初始化时间戳  
    Hash[1] = 0;        //初始化根结点的哈希值，其他结点的哈希值均可根据根结点求出  
}  
  
void dfs(int x){  
    in[x] = ++dfs_clock;        //编号  
    maxChild[x] = x;     //预设最大为自己（叶子就如此而已了）  
    tail[x] = 0;        //先假设为叶子，若实际上不是叶子，下面的递归会更新tail的值  
    Rank[x] = tripRank[x2trip[x]];      //把名次映射过来  
    for(int e = head[x]; e != -1; e = nxt[e]){  
        Hash[v[e]] = ((long long)Hash[x] * 26 + w[e]) % mod;        //计算哈希值，这个别放dfs(v[e])下面，因为dfs(v[e])需要用到Hash[v[e]]  
        dfs(v[e]);  
        tail[x] = max(tail[x], tail[v[e]]+1);  
        if(in[maxChild[v[e]]] > in[maxChild[x]]) maxChild[x] = maxChild[v[e]];  
    }  
    dep[height[x]].push_back(x);     //加入对应层次的dep[]中，这个别放在for的前面，因为push_back是头插入的  
}  
  
void get(){        //获得a[]和depBefore[]  
    int cnt = 1;  
    depBefore[0] = 0;       //别漏了  
    for(int i = 1; i <= maxHeight; i++){  
        int sz = dep[i].size();  
        for(int j = 0; j < sz; j++) a[cnt++] = dep[i][j];  
        depBefore[i] = depBefore[i-1] + sz;  
    }  
}  
  
void initRMQ(){     //初始化RMQ  
    for(int i = 1; i <= N; i++) d[i][0] = a[i];  
    for(int j = 1; (1<<j) <= N; j++)  
        for(int i = 1; i + (1 << j) - 1 <= N; i++)  
            if(Rank[d[i][j-1]] > Rank[d[i+(1<<(j-1))][j-1]]) d[i][j] = d[i][j-1];       //根据字典序名次来比较  
            else d[i][j] = d[i+(1<<(j-1))][j-1];  
}  
  
int RMQ(int L, int R){      //RMQ求最值，返回的是[L, R]内字典序最大的原结点编号  
    int k = 0;  
    while(1<<(k+1) <= R - L + 1) k++;  
    if(Rank[d[L][k]] > Rank[d[R-(1<<k)+1][k]]) return d[L][k];  
    else return d[R-(1<<k)+1][k];  
}  
  
void read(){  
    int uu, vv;  
    char ww;  
    scanf("%d", &N);  
    for(int i = 1; i < N; i++){  
        scanf("%d%d %c", &uu, &vv, &ww);  
        addEdge(uu, vv, ww-'a');  
        fa[vv] = uu;  
    }  
    scanf("%d", &M);  
}  
  
bool cmp(int a, int b){     //同一层深度中按dfs先后排序  
    return in[a] < in[b];  
}  
  
int solve(int u, int m){  
    if(m > tail[u]) return -1;      //要走的步数大于结点u到叶子结点的距离时IMPOSSIBLE  
    int h = height[u] + m;        //目标结点的深度  
    int L = lower_bound(dep[h].begin(), dep[h].end(), u, cmp) - dep[h].begin() + 1 + depBefore[h-1];  
    int R = upper_bound(dep[h].begin(), dep[h].end(), maxChild[u], cmp) - dep[h].begin() + depBefore[h-1];  
    return RMQ(L, R);  
}  
  
int main()  
{  
    getPow26();  
    scanf("%d", &T);  
    while(T--){  
        init();     //为输入，bfs和获取trip树结点的字典序初始化  
        read();     //读入数据  
        bfs();      //求得树各结点的深度，建trip  
        getTripRank(0);     //获取trip树结点的字典序  
        init2();        //为dfs初始化  
        dfs(1);     //求得in[], maxChild[], tail[], Hash[], Rank[], dep[]  
        get();      //求得a[], depBefore[]  
        initRMQ();  
        while(M--){  
            int u, m;  
            scanf("%d%d", &u, &m);  
            int des = solve(u, m);      //求得目标结点  
            if(des != -
补充：软件开发 , C++ ,