题目链接  2018广东工业大学校赛  Problem B

考虑到每条边的权值变化$26$个时刻之后一定会回到原来的状态。

那么预处理出前$26$个时刻每棵树的形态,对每棵树做一遍字符串哈希。

查询的时候找到满足$x$往上爬$k$步和$y$往上爬$k$步之后面对的边的边权不一样的时候的$k$的最小值。

那么比较这条不一样的边的权值就好了。这个过程用倍增实现即可。

时间复杂度$O(nlogn)$

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)    for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i) typedef unsigned long long LL; const int N = 1e5 + 10;
const int A = 20;
const LL base = 233; int T;
int n, q;
int a[N], c[N], deep[N], f[N][A], g[26][N];
LL val[30];
LL bin[N], h[29][N];
LL seed = 87378051;
vector <int> v[N]; inline LL rnd(){ return seed = seed * 17 + 23;} void dfs(int x, int dep){
deep[x] = dep; for (auto u : v[x]){
int w = a[u];
rep(i, 0, 25){
int z = (w + i * c[u]) % 26;
g[i][u] = z;
h[i][u] = h[i][x] * base + val[z];
}
dfs(u, dep + 1);
}
} int main(){ rep(i, 0, 26) val[i] = rnd() * rnd() * rnd();
bin[0] = 1;
rep(i, 1, 1e5 + 1) bin[i] = bin[i - 1] * base; scanf("%d", &T);
while (T--){
memset(f, 0, sizeof f);
memset(h, 0, sizeof h);
memset(g, 0, sizeof g);
scanf("%d", &n);
rep(i, 0, n + 1) v[i].clear();
rep(i, 2, n){
int x, k;
char ch[2];
scanf("%d%s%d", &x, ch, &k);
a[i] = ch[0] - 'a';
c[i] = k;
f[i][0] = x;
v[x].push_back(i);
} rep(i, 0, 25) g[i][1] = -1;
dfs(1, 0); rep(i, 1, n) rep(j, 0, 18) f[i][j + 1] = f[f[i][j]][j]; scanf("%d", &q);
while (q--){
int x, y, t;
scanf("%d%d%d", &x, &y, &t);
t %= 26; int dep = min(deep[x], deep[y]);
int z = 1, m = 0;
for (; (z << 1) <= dep; z <<= 1) ++m; dec(i, m, 0){
int fx = f[x][i], fy = f[y][i];
int now = 1 << i;
LL hx = h[t][x] - h[t][fx] * bin[now];
LL hy = h[t][y] - h[t][fy] * bin[now];
if (hx == hy){
x = fx;
y = fy;
}
} if (g[t][x] < g[t][y]) puts("<");
else if (g[t][x] > g[t][y]) puts(">");
else puts("=");
}
} return 0; }

最新文章

  1. IBM X3850 Windows 无法安装到这个磁盘。选中的磁盘具有MBR分区表。在 EFI 系统上,Windows 只能安装到 GPT 磁盘
  2. 最简实例说明wait、notify、notifyAll的使用方法
  3. vs 2012 智能提示后为何不能 直接按enter键把提示的内容输入
  4. 【img】 图片是怎么存储的
  5. IOS版UC我的视频地址
  6. POJ2689 - Prime Distance(素数筛选)
  7. C#实现发送邮件
  8. Spring事务隔离级别与传播机制详解,spring+mybatis+atomikos实现分布式事务管理
  9. [转载] ZooKeeper原理及使用
  10. RecyclerView 实现gallery画廊效果
  11. Ubuntu版本linux系统安装git
  12. h5-audio/video标签
  13. css背景色半透明的最佳实践
  14. LA 2218 Triathlon(半平面交)
  15. 用命令bat打开某个文件或文件夹
  16. 解决git中文乱码问题
  17. 8.4 正睿暑期集训营 Day1
  18. 解决appcompat中各种奇葩的错误
  19. Mock 模拟测试简介及 Mockito 使用入门
  20. 使用webbench做压力测试

热门文章

  1. python学习笔记-基础
  2. Python全栈工程师
  3. 指定user镜像安装的磁盘
  4. 最干净的pyinstaller打包成exe应用程序方法
  5. XGBoost——机器学习--周振洋
  6. Extjs msgTarget 提示位置
  7. git使用及一些配置、问题
  8. 重复造轮子系列--内存池(C语言)
  9. Java进行身份证格式强校验(准)
  10. 【bzoj2618】[Cqoi2006]凸多边形 半平面交