挺有意思的一道题，思路肯定是将图转化为Trie树，这样可以求得字典序。
然后，按照trie的层次求解。一直wa的原因在于将树转化为线性数据结构时要从原树遍历，从trie遍历就会wa。不同结点可能映射为trie上的同一结点，如
1->2 (a) 1->3(a) 2->4(b), 这是trie的结构是RT->a->b。然而，从结点3不能找到权重为b的路径。
用RMQ求满足边界的rank最大值，通过sa找到该最大值对应的trie上的根。从而求解。

/* 4601 */
#include
#include
#include
#include

#define sti set
#define stpii set >
#define mpii map
#define vi vector
#define pii pair
#define vpii vector >
#define rep(i, a, n) for (int i=a;i=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
// #define DEBUG

typedef struct {
int u, v, w;
int nxt;
} edge_t;

typedef struct ques_t {
int u, m, id;

 ques\_t() {}  
 friend bool operator< (const ques\_t& a, const ques\_t& b) {  
     if (a.m == b.m)  
         return a.id < b.id;  
     return a.m < b.m;  
 }

} ques_t;

const int mod = 1e9+;
const int maxn = 1e5+;
const int maxv = maxn;
const int maxe = maxv * ;
int head[maxv], m;
edge_t E[maxe];
int nxt[maxn][], l;
int Pos[maxv], Rank[maxv], sa[maxv];
__int64 Base[maxn];
__int64 Val[maxn];
int deep[maxv];
int fr[maxv], to[maxv];
int dfs_clock;
vi layer[maxn];
int maxd;
int n, qn, q;
ques_t Qu[maxn];
int ans[maxn];
int dp[][maxn];
int D[maxn];

void Init() {
Base[] = ;
rep(i, , maxn)
Base[i] = Base[i-] * % mod;
}

void init() {
memset(head, -, sizeof(head));
m = ;
memset(nxt[], , sizeof(nxt[]));
l = ;
dfs_clock = ;
maxd = ;
rep(i, , n+)
layer[i].clr();
}

int newNode() {
++l;
memset(nxt[l], , sizeof(nxt[l]));
Val[l] = ;
return l;
}

void addEdge(int u, int v, int w) {
E[m].v = v;
E[m].w = w;
E[m].nxt = head[u];
head[u] = m++;

 E\[m\].v = u;  
 E\[m\].w = w;  
 E\[m\].nxt = head\[v\];  
 head\[v\] = m++;  

}

void Build_Trie(int u, int fa, int rt) {
int v, k, p;

 Pos\[u\] = rt;  
 for (k=head\[u\]; k!=-; k=E\[k\].nxt) {  
     v = E\[k\].v;  
     if (v == fa)  
         continue;

     int id = E\[k\].w;  
     p = nxt\[rt\]\[id\];  
     if (!p)  
         p = nxt\[rt\]\[id\] = newNode();  
     Build\_Trie(v, u, p);  
 }  

}

void Mark_Rank(int rt, int d) {
int p;

 Rank\[rt\] = ++dfs\_clock;  
 sa\[dfs\_clock\] = rt;  
 rep(i, , ) {  
     p = nxt\[rt\]\[i\];  
     if (p) {  
         Val\[p\] = (Val\[rt\]\* + i) % mod;  
         Mark\_Rank(p, d+);  
     }  
 }  

}

void calDepth(int u, int fa, int rt) {
int v, k, p;

 D\[++dfs\_clock\] = Rank\[rt\];  
 fr\[u\] = dfs\_clock + ;  
 maxd = max(deep\[u\], maxd);  
 layer\[deep\[u\]\].pb(dfs\_clock);  
 for (k=head\[u\]; k!=-; k=E\[k\].nxt) {  
     v = E\[k\].v;  
     if (v == fa)  
         continue;  
     deep\[v\] = deep\[u\] + ;  
     p = nxt\[rt\]\[E\[k\].w\];  
     calDepth(v, u, p);  
 }  
 to\[u\] = dfs\_clock;  

}

void init_RMQ(int d, int n) {
int i, j;

 for (i=; i<n; ++i)  
     dp\[\]\[i\] = D\[layer\[d\]\[i\]\];  
 for (j=; (<<j)<=n; ++j)  
     for (i=; i+(<<j)-<n; ++i)  
         dp\[j\]\[i\] = max(dp\[j-\]\[i\], dp\[j-\]\[i+(<<(j-))\]);  

}

int RMQ(int l, int r) {
if (l > r)
swap(l, r);

 int k = ;

 while ((<<(k+)) <= r-l+)  
     ++k;

 return max(dp\[k\]\[l\], dp\[k\]\[r-(<<k)+\]);  

}

int calc(int qid, int d) {
int u = Qu[qid].u;
int rt = Pos[u];
int b = fr[u];
int e = to[u];
int l = lower_bound(all(layer[d]), b) - layer[d].begin();
int r = upper_bound(all(layer[d]), e) - layer[d].begin();
--r;

 if (l > r)  
     return -;

 int mxrank = RMQ(l, r);  
 int mxrt = sa\[mxrank\];  
 int delta = d - deep\[u\];  
 int ret = (Val\[mxrt\] - Val\[rt\] \* Base\[delta\] % mod + mod) % mod;

 return ret;  

}

void solve() {
Build_Trie(, , );
Mark_Rank(, );
dfs_clock = ;
deep[] = ;
calDepth(, , );

 scanf("%d", &q);  
 qn = ;  
 rep(i, , q) {  
     scanf("%d %d", &Qu\[qn\].u, &Qu\[qn\].m);  
     int deepu = deep\[Qu\[qn\].u\];  
     if (Qu\[qn\].m == ) {  
         ans\[i\] = ;  
     } else if (deepu+Qu\[qn\].m > maxd) {  
         ans\[i\] = -;  
     } else {  
         Qu\[qn\].m += deepu;  
         Qu\[qn\].id = i;  
         ++qn;  
     }  
 }

 if (qn) {  
     sort(Qu, Qu+qn);  
     int j = ;  
     rep(i, , maxd+) {  
         if (i < Qu\[j\].m)  
             continue;  
         int sz = SZ(layer\[i\]);  
         init\_RMQ(i, sz);  
         while (j<=qn && Qu\[j\].m==i) {  
             int id = Qu\[j\].id;  
             ans\[id\] = calc(j, i);  
             ++j;  
         }  
         if (j == qn)  
             break;  
     }  
 }

 rep(i, , q) {  
     if (ans\[i\] == -)  
         puts("IMPOSSIBLE");  
     else  
         printf("%d\\n", ans\[i\]);  
 }  

}

int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif

 int t;  
 int u, v;  
 char ws\[\];

 Init();  
 scanf("%d", &t);  
 while (t--) {  
     scanf("%d", &n);  
     init();  
     rep(i, , n) {  
         scanf("%d %d %s", &u, &v, ws);  
         addEdge(u, v, ws\[\]-'a');  
     }  
     solve();  
 }

 #ifndef ONLINE\_JUDGE  
     printf("time = %d.\\n", (int)clock());  
 #endif

 return ;  

}

数据发生器。

from random import randint, shuffle
import shutil
import string

def GenDataIn():
with open("data.in", "w") as fout:
t = 10
bound = 10**3
lc = list(string.lowercase)
fout.write("%d\n" % (t))
for tt in xrange(t):
n = randint(300, 500)
fout.write("%d\n" % (n))
ust = [1]
vst = range(2, n+1)
for i in xrange(1, n):
uid = randint(0, len(ust)-1)
vid = randint(0, len(vst)-1)
u = ust[uid]
v = vst[vid]
ust.append(v)
vst.remove(v)
idx = randint(0, 25)
c = lc[idx]
fout.write("%d %d %s\n" % (u, v, c))
q = randint(400, 600)
fout.write("%d\n" % (q))
for i in xrange(q):
u = randint(1, n+1)
m = randint(0, 10)
fout.write("%d %d\n" % (u, m))

def MovDataIn():
desFileName = "F:\eclipse_prj\workspace\hdoj\data.in"
shutil.copyfile("data.in", desFileName)

if __name__ == "__main__":
GenDataIn()
MovDataIn()