python入门
英语
功能测试
java加密算法
脑科学
亚马逊证书
self-attention
java项目实战
后断开发
语言模型
后台
状态模式
符号表导出
二元操作符
菜鸟日记
计算机软件考试
IO流中的属性集
研究报告
keras
数字IC设计
dfs序
2024/4/23 13:51:09![bzoj 1146: [CTSC2008]网络管理Network](/images/no-images.jpg)
bzoj 1146: [CTSC2008]网络管理Network
Description M公司是一个非常庞大的跨国公司，在许多国家都设有它的下属分支机构或部门。为了让分布在世界各地的N个部门之间协同工作，公司搭建了一个连接整个公司的通信网络。该网络的结构由N个路由器和N-1条高速光缆组成。每个部门都有一个专属的路由器…
2016多校训练Contest4: 1007 Treasure hdu5770
Problem Description?? has got a treasure map,the treasure map consists of N nodes,there are N-1 bidirectional roads, Each of them connects a pair of nodes,the N nodes are all connected by the N-1 bidirectional roads.?? can travel through the roads.Ther…
![【树上差分】【dfs序】【线段树】P4216 [SCOI2015]情报传递](https://img-blog.csdnimg.cn/953b1d5a18c040db946d29a094f486b3.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAYW5keWNfMDM=,size_20,color_FFFFFF,t_70,g_se,x_16)
【树上差分】【dfs序】【线段树】P4216 [SCOI2015]情报传递
题意 分析
对于第 i 次询问相当于路径上有多少个点在时间 i-c 之前就开始加 1 了
那么我们把询问离线，问题就转换成了树上单点加，询问差分路径
这种不需要树剖，1只log就可以解决
f(u)表示u到根的路径和，这样每次单点修改影响的…
备战蓝桥杯---树学初步1
LCA（最近公共祖先）
定义：有根树的两个节点u,v，他们的LCA是一个节点x,其中x是他们的公共祖先并且X的深度尽可能大。
法1---Tarjan算法：
核心：DFS并查集
在并查集中建立仅有u的集合，设该集合祖…
[bzoj3729]Gty的游戏
Description
给定一棵n个节点的数，第i个节点上有ai个石子。 有两个人在van游戏，每次操作者可以从x的子树中的任意一个点选择不超过m个石子移动到它的父亲。 给定t次操作，每次操作询问为x的子树中做游戏先手是否必胜，或者修改一…
bzoj 4034: [HAOI2015]T2
Description 有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个 操作，分为三种：操作 1 ：把某个节点 x 的点权增加 a 。操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 &#x…
5-14 数据结构啊poi E.splay上的游戏
http://acm.hust.edu.cn/vjudge/contest/view.action?cid78124#problem/E //想看题目的willinglive 我们发现无论如何操作。树的中序遍历不变 于是我们维护中序遍历，每次左旋或者右旋只改变两个点的状态 然后记录下他的子树是哪段，用线段树维护区间乘积…
![bzoj 3052: [wc2013]糖果公园](http://www.lydsy.com/JudgeOnline/upload/201302/6%281%29.jpg)
bzoj 3052: [wc2013]糖果公园
Description Input Output Sample Input Sample Input Sample Output 84 131 27 84HINT bzoj上总时限是250S。考试时单点10S 这题可以用莫队来做。先求出dfs序。然后把树上询问改成在dfs序上的区间询问。然后就和队列的莫队一样了。 以左端点，右端点，时间…
[bzoj2819]Nim
Description
给出一棵树，每次修改一个点的值或询问x,y之间的路径上的数组成的石子游戏先手有没有必胜方案。（普通版SG） n,m<5*10^5
Solution
哎呀，dfs带一个参过~(≧▽≦)/~啦啦啦 虽然很对不起vfleaking爷，但…
计蒜客 青出于蓝胜于蓝 dfs序+树状
思路：建立dfs序后，利用树状数组(或线段树)先把当前名次所在区间加1，然后求dfs序区间值的差，即答案。
#include <iostream>
#include <cmath>
#include <cctype>
#include <cstring>
#include <algorit…
DFS序和欧拉序的降维打击
1. DFS 序和时间戳
1.1 DFS 序
定义：树的每一个节点在深度优先遍历中进、出栈的时间序列。
如下树的 dfs 序就是[1,2,8,8,5,5,2,4,3,9,9,3,6,6,4,7,7,1]。 下图为生成DFS的过程。对于一棵树进行DFS序，除了进入当前节点时对此节点进行记录，…
Codeforces Round #746 (Div. 2) D. Hemose in ICPC ? 交互 dfs序 + 二分
题目链接
https://codeforces.com/problemset/problem/1592/D
题目大意
一道交互题
给你一个生成树 每个节点之间的边的值 是两个节点值的gcd
你可以问最多12次
每次提出询问k个节点里最大的边值是多少
题目思路
我一开始想的是从点去考虑问题 类似于树上搜索这种 但是…