题意：一棵N个结点的有根树，根结点为1，每条边有一个小写字母作为权值，现有M个询问，每个询问是从树中的一个结点u开始，沿着其子孙走m步，走出的路径的字典序最大的路径哈希值（2 <= N <= 10^5, 1 <= M <= 10^5, 1 <= m <= 10^5）。
题目链接：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; //根结点的高度设为1memset(ch, 0, sizeof(ch)); //初始化所有trip结点int sz = 1; //trip目前结点个数x2trip[1] = 0; //原根结点1对应trip根结点0qu.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(){ //初始化RMQfor(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到叶子结点的距离时IMPOSSIBLEint 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(); //求得树各结点的深度，建tripgetTripRank(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 != -1) printf("%d\n", (int)(Hash[des] - (long long)Hash[u] * pow26[m] % mod + mod) % mod);else puts("IMPOSSIBLE");}}return 0;
}