C++14(g++5.4) 解法, 执行用时: 162ms, 内存消耗: 40036K, 提交时间: 2019-02-28 11:03:05
/*
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<cmath>
#define ll long long
#define M 100010
#define mmp make_pair
using namespace std;
const int base = 127;
int read() {
int nm = 0, f = 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
return nm * f;
}
const int mod = 1000000007;
ll poww[M];
char op[11];
int fa[M][18], b[M], a[M], n, deep[M];
ll hh[27][M];
vector<int> to[M];
void dfs(int now) {
for(int i = 0; i < to[now].size(); i++) {
int vj = to[now][i];
deep[vj] = deep[now] + 1;
for(int i = 0, ch = a[vj]; i < 26; i++, (ch += b[vj])) {
if(ch >= 26) ch -= 26;
hh[i][vj] = (hh[i][now] * base + ch) % mod;
}
dfs(vj);
}
}
int main() {
poww[0] = 1;
for(int i = 1; i < M; i++) poww[i] = poww[i - 1] * base % mod;
int t = read();
while(t--) {
n = read();
for(int i = 2; i <= n; i++) {
fa[i][0] = read();
scanf("%s", op);
b[i] = read();
to[fa[i][0]].push_back(i);
a[i] = op[0] - 'a';
b[i] %= 26;
}
for(int i = 1; 1 << i <= n; i++)
for(int j = 1; j <= n; j++)
fa[j][i] = fa[fa[j][i - 1]][i - 1];
dfs(1);
int q = read();
while(q--) {
int vi = read(), vj = read(), v = read() % 26;
for(int i = 17; i >= 0; i--) {
if(min(deep[vi], deep[vj]) < (1 << i)) continue;
ll ih = (hh[v][vi] - hh[v][fa[vi][i]] * poww[1 << i] % mod + mod) % mod;
ll jh = (hh[v][vj] - hh[v][fa[vj][i]] * poww[1 << i] % mod + mod) % mod;
if(ih == jh) vi = fa[vi][i], vj = fa[vj][i];
}
int aa = (a[vi] + v * b[vi]) % 26, bb = (a[vj] + v * b[vj]) % 26;
if(aa < bb) puts("<");
if(aa == bb) puts("=");
if(aa > bb) puts(">");
}
for(int i = 1; i <= n; i++) to[i].clear();
}
return 0;
}
/*
2
10
1 a 1
1 a 5
1 c 2
2 f 2
3 a 5
3 e 3
4 b 1
5 z 1
7 o 2
4
5 7 0
5 7 2
9 10 1
8 8 8
10
1 a 1
1 a 5
1 c 2
2 f 2
3 a 5
3 e 3
4 b 1
5 z 1
7 o 2
4
5 7 0
5 7 2
9 10 1
8 8 8
*/
C++11(clang++ 3.9) 解法, 执行用时: 211ms, 内存消耗: 13144K, 提交时间: 2019-02-02 15:28:56
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')w=0,ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
#define ll unsigned long long
const int N=1e5+5;
const ll base=20020415;
int T,n,q,nxt[N],head[N],ch[N],k[N],fa[N][18],u[N],v[N],ans[N];
ll pw[18],hsh[N];char sgn[]={'>','=','<'};
vector<int>id[26];
void dfs(int u){
for(int j=1;j<18;++j)fa[u][j]=fa[fa[u][j-1]][j-1];
for(int v=head[u];v;v=nxt[v])dfs(v);
}
void dfs(int u,int t){
for(int v=head[u];v;v=nxt[v])
hsh[v]=hsh[u]*base+(ch[v]+k[v]*t)%26+233,dfs(v,t);
}
ll cal(int u,int j){
return hsh[u]-hsh[fa[u][j]]*pw[j];
}
int main(){
pw[0]=base;
for(int i=1;i<18;++i)pw[i]=pw[i-1]*pw[i-1];
T=gi();while(T--){
n=gi();memset(head,0,sizeof(head));
for(int i=2,f;i<=n;++i){
fa[i][0]=f=gi();ch[i]=getchar()-'a';k[i]=gi()%26;
nxt[i]=head[f];head[f]=i;
}
dfs(1);q=gi();
for(int i=0;i<26;++i)id[i].clear();
for(int i=1;i<=q;++i){
u[i]=gi();v[i]=gi();
id[gi()%26].push_back(i);
}
for(int t=0;t<26;++t){
dfs(1,t);
for(int i:id[t]){
int x=u[i],y=v[i];
for(int j=17;~j;--j)
if(cal(x,j)==cal(y,j))
x=fa[x][j],y=fa[y][j];
if(cal(x,0)==cal(y,0))ans[i]=1;
else if(cal(x,0)<cal(y,0))ans[i]=2;
else ans[i]=0;
}
}
for(int i=1;i<=q;++i)putchar(sgn[ans[i]]),putchar('\n');
}
return 0;
}
