[CF191C]Fools and Roads
2024-08-22 21:00:58
题目大意:有一颗$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;
}
最新文章
- Machine Learning Algorithms Study Notes(1)--Introduction
- Python3.5连接Mysql
- ScriptX.cab打印控件的使用,控件文件里有
- 业界最有价值的 ASP.NET 博文汇总
- kernel 于ioctl申请书
- unity 创建NGUI字体
- Centos/RHEL上查看主板型号
- angularjs select一些坑
- gdbserver移植到DM368板子上的过程 以及segment fault problem
- Linux 学习 (六) 关机与重启命令
- JS33个概念
- zabbix http服务监控实例
- springboot 项目中获取默认注入的序列化对象 ObjectMapper
- Ubuntu14.04 LTS 安装Chrome浏览器(转)
- UVA-10273 Cyborg Genes (DP)
- 可视化的Redis数据库管理工具redis-desktop-manager的初步使用(图文详解)
- WIN 10 初体验:期待越多失望越大
- EntityFramework定向加载实体
- Jinja2 及 render_template 的深度用法
- 初学SSM遇到的BUG
热门文章
- Mantle--国外程序员最常用的iOS模型&;字典转换框架
- Spring 中IOC(控制反转)&;&; 通过SET方式为属性注入值 &;&; Spring表达式
- linux下安装xtrabackup
- python错误处理之try...except...finally...错误处理机制。
- python中的字典内置方法小结
- .c和.h区别
- urllib使用一
- TCP重组问题
- swoole创建websocket服务器
- 容器技术的落地还要依靠SDN