目大意:有一颗$n$个节点的树,$k$次旅行,问每一条被走过的次数。

题解:树上差分,$num_x$表示连接$x$和$fa_x$的边被走过的次数,一条路径$u->v$,$num_u+1,num_v+1,num_{LCA(u,v)}-2$,最后求个子树和就行了

卡点:

C++ Code:

#include <cstdio>
#include <algorithm>
#define maxn 100010 int head[maxn], cnt = 1;
struct Edge {
int to, nxt;
} e[maxn << 1];
inline void add(int a, int b) {
e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt;
} #define M 18
int dep[maxn], fa[M][maxn];
void dfs(int u) {
for (int i = 1; i < M; i++) fa[i][u] = fa[i - 1][fa[i - 1][u]];
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (!dep[v]) {
dep[v] = dep[u] + 1;
fa[0][v] = u;
dfs(v);
}
}
}
inline int LCA(int x, int y) {
if (x == y) return x;
if (dep[x] < dep[y]) std::swap(x, y);
for (int i = dep[x] - dep[y]; i; i &= i - 1) x = fa[__builtin_ctz(i)][x];
if (x == y) return x;
for (int i = M - 1; ~i; i--) if (fa[i][x] != fa[i][y]) x = fa[i][x], y = fa[i][y];
return fa[0][x];
} int V[maxn];
void dfs1(int u) {
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (v != fa[0][u]) {
dfs1(v);
V[u] += V[v];
}
}
} int n, k;
int main() {
scanf("%d", &n);
for (int i = 1, a, b; i < n; i++) {
scanf("%d%d", &a, &b);
add(a, b);
add(b, a);
}
dep[1] = 1; dfs(1);
scanf("%d", &k);
for (int i = 0, a, b; i < k; i++) {
scanf("%d%d", &a, &b);
V[a]++, V[b]++, V[LCA(a, b)] -= 2;
}
dfs1(1);
for (int i = 2; i <= cnt; i += 2) {
int u = e[i ^ 1].to, v = e[i].to;
if (dep[u] < dep[v]) std::swap(u, v);
printf("%d", V[u]); putchar((i ^ 1) == cnt ? '\n' : ' ');
}
return 0;
}

  

最新文章

  1. Machine Learning Algorithms Study Notes(1)--Introduction
  2. Python3.5连接Mysql
  3. ScriptX.cab打印控件的使用,控件文件里有
  4. 业界最有价值的 ASP.NET 博文汇总
  5. kernel 于ioctl申请书
  6. unity 创建NGUI字体
  7. Centos/RHEL上查看主板型号
  8. angularjs select一些坑
  9. gdbserver移植到DM368板子上的过程 以及segment fault problem
  10. Linux 学习 (六) 关机与重启命令
  11. JS33个概念
  12. zabbix http服务监控实例
  13. springboot 项目中获取默认注入的序列化对象 ObjectMapper
  14. Ubuntu14.04 LTS 安装Chrome浏览器(转)
  15. UVA-10273 Cyborg Genes (DP)
  16. 可视化的Redis数据库管理工具redis-desktop-manager的初步使用(图文详解)
  17. WIN 10 初体验:期待越多失望越大
  18. EntityFramework定向加载实体
  19. Jinja2 及 render_template 的深度用法
  20. 初学SSM遇到的BUG

热门文章

  1. Mantle--国外程序员最常用的iOS模型&amp;字典转换框架
  2. Spring 中IOC(控制反转)&amp;&amp; 通过SET方式为属性注入值 &amp;&amp; Spring表达式
  3. linux下安装xtrabackup
  4. python错误处理之try...except...finally...错误处理机制。
  5. python中的字典内置方法小结
  6. .c和.h区别
  7. urllib使用一
  8. TCP重组问题
  9. swoole创建websocket服务器
  10. 容器技术的落地还要依靠SDN