题意: 这题想了挺久的, 参考了kuangbin大神的代码:https://www.cnblogs.com/kuangbin/archive/2012/08/28/2659915.html 给出树上边的长度, 求出每一个点的最长距离(就是求这个点到某一个叶子结点的距离, 这个距离最长). 分析: 结点u的最长路径, 其实就是max( u到子树叶子的最长路径,  u到父亲的距离 + 父亲子树的最长路径). 注意, 因为父亲子树的最长路径可能会经过u, 这样这个状态就不能用 u到父亲的距离 + 父亲

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2196 思路:首先任意一次dfs求出树上最长直径的一个端点End,然后以该端点为起点再次dfs求出另一个端点,然后再次以求出的另一个端点为起点dfs,每次做dfs的时候都更新dist[](dist[u]表示u到树上任意节点的最远距离),可以证明树上任意某个节点到树上任意节点的最远距离的端点一定会是树上直径的两个端点之一. #include<iostream> #include<cstdio&g

乍一看题意比较麻烦,好像要删点求联通性,但其实是相当于求以某一个节点为根时,他的所有后代(儿子,儿子的儿子等等)的儿子的总和最大. 两边dfs即可,第一遍dfs随便找一个点为根,求出每个节点的儿子数siz[],第二遍dfs以每个点作为根更新ans. 这里注意:如果u为根,u是v的父亲,且此时u后代的和为siz[u] = val,那么v为根时后代和为val-siz[v]+n-siz[v],以此关系作为第二遍dfs的依据. #include <bits/stdc++.h> using namesp

题意: 给你一棵有n个节点的树,树的边权都是1. 有m次询问,每次询问输出树上所有节点离其较近结点距离的最大值. 思路: 1.首先是按照常规树形dp的思路维护一个子树节点中距离该点的最大值son_dis[i],维护非子树节点中距离该点的最大值fa_dis[i]; 2.对于每个节点维护它最大的三个儿子节点的son_dis; 3.维护up[i][j]和down[i][j]数组,这个类似倍增lca里边的fa[i][j],up[i][j]代表的含义是从第j个点向上到它的第2^i个父节点这条链上的点除了该

昨天做了HNOI day 2,感觉好像还是可做的,想当年什么splay还是高级算法,现在点剖什么就老考了简直丧病,虽然第二题还没写那就先当下嘴巴选手吧= = T1:[HNOI2015]落忆枫音 描述:http://www.lydsy.com/JudgeOnline/problem.php?id=4011 这道题还是挺神奇的,首先如果是个DAG的话我们可以把所有点的入度相乘就得到答案. 那么现在加上了一条边x->y,也就是说答案=原来的答案+用上这条边的答案, 我们可以发现,如果我们把x到根的链拿

正解:虚树 解题报告: 传送门! 首先看到这种就要想到虚树这个是毫无疑问的QwQ 建虚树什么的都可以循规蹈矩地做,不说辣,具体可以看下虚树学习笔记什么的看下板子 但是建好虚树之后怎么搞还是有点儿讲究,所以专门开个题解港下(所以为什么好多人拿这个当做虚树入门题什么的昂,,,大概我太菜辣所以只有理解了半天趴QAQ(我我我我在网上找题解看到好多都是说,"首先求值很容易balabala",,,就很绝望,,,可能真的我太菜辣QAQ 首先读入dfs然后建虚树什么的跳过,直接到计算答案的地方 这里主

解题思路: 求出树的直径的两个端点.则树上每一个节点到其它点的最远距离一定是到这两个端点的距离中最长的那一个. #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <vector> #include <queue> #define LL long long using na

Codeforces Round #588 (Div. 2)-E. Kamil and Making a Stream-求树上同一直径上两两节点之间gcd的和 [Problem Description] 给你一棵树,树上每个节点都有一个权值.定义\(1\sim v\)的最短路径所经过的所有节点\(u\)称为\(v\)节点的祖先.定义函数\(f(u,v)=gcd(u,t1,t2,\dots,v)\),其中\(u,t1,t2,\dots\)都是\(v\)的祖先.求\(\sum f(u,v)\). [

暴力树剖做法显然,即使做到两个log也不那么优美. 考虑避免树剖做到一个log.那么容易想到树上差分,也即要对每个点统计所有经过他的路径产生的总贡献(显然就是所有这些路径端点所构成的斯坦纳树大小),并支持在一个log内插入删除合并. 考虑怎么求树上一些点所构成的斯坦纳树大小.由虚树的构造过程容易联想到,这就是按dfs序排序后这些点的深度之和-相邻点的lca的深度之和(首尾视作相邻),也就相当于按dfs序遍历所有要经过的点并回到原点的路径长度/2. 这个东西显然(应该)可以set启发式合并维护,但

主要是记录思路,不要被刚开始错误方向带偏了 www 「CF1110F」Nearest Leaf 特殊性质:先序遍历即为 \(1 \to n\),可得出:叶子节点编号递增或可在不改变树形态的基础上调整为递增. 这样就可找出区间 \([l, r]\) 中的叶子节点有哪些了,预处理深度,暴力 \(O(n ^ 2)\). 考虑柿子 \(\min \{\mathrm{d} (y) - \mathrm{d} (\mathrm{f} (x))\}\),其中 \(d(x)\) 表示深度,\(f(x)\) 表示父

题目链接:http://poj.org/problem?id=2763 思路:首先求出树上dfs序列,并且标记树上每个节点开始遍历以及最后回溯遍历到的时间戳,由于需要修改树上的某两个节点之间的权值,如果parent[v] = u, 那么说明修改之后的v的子树到当前根的距离都会改变,由于遍历到v时有开始时间戳以及结束时间戳,那么处于这个区间所有节点都会影响到,于是我们可以通过数组数组来更新某个区间的值,只需令从区间起始点之后的每个值都增加一个改变量了,令区间中止点之后的每个值都减小一个改变量,这样

1353: 结点选择 时间限制: 1 Sec  内存限制: 128 MB提交: 6  解决: 2[提交][状态][讨论版] 题目描述 问题描述 有一棵 n 个节点的树,树上每个节点都有一个正整数权值.如果一个点被选择了,那么在树上和它相邻的点都不能被选择.求选出的点的权值和最大是多少? 选择3.4.5号点,权值和为 3+4+5 = 12 . 数据规模与约定 对于20%的数据, n <= 20. 对于50%的数据, n <= 1000. 对于100%的数据, n <= 100000. 权值

题目链接:http://lightoj.com/volume_showproblem.php?problem=1257 思路:首先需要用到一个知识点就是树上任一点到树上最长直径的某一个端点的距离最远,因此我们可以用dp[u]表示从u点出发到的最远距离,然后从任意一点出发,一遍dfs求出树上最长直径的某一个端点,然后从这个端点出发,再次dfs求出另一个端点,最后在从求出的端点出发进行dfs更新.每次做dfs时都更新一下dp. #define _CRT_SECURE_NO_WARNINGS #inc

Computer Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4440    Accepted Submission(s): 2236 Problem Description A school bought the first computer some time ago(so this computer's id is 1). Du

描述 A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路.每一条道路对车辆都有重量限制,简称限重.现在有 q 辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物. 格式 输入格式 第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道路. 接下来 m 行每行 3 个整数 x.y.z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z 的道路.注意:x 不等于 y,两座城市之间可能有多条道路. 接

背景 在做一个类似文件树的控件,支持节点从树上向其它的控件拖动程序,但是要保证树上的节点不能拖动上其他的节点上. 代码 /// <summary> /// 拖动节点完成 /// </summary> /// <param name="sender"></param> /// <param name="e"></param> private void treeList_ShowProjectFol

链接:https://codeforces.com/contest/161/problem/D 题意:给一个树,求距离恰好为$k$的点对是多少 题解:对于一个树,距离为$k$的点对要么经过根节点,要么跨过子树的根节点,于是考虑树分治 用类似poj1741的想法,可以推出: 对于任意一棵子树,其根节点记为$C$,其子树中: 记距离$C$距离之和为$k$的点对数量$S_{c}$ 记$C$儿子节点$C_1...C_n$的子树中,距离$C_i$距离为$k-2$的点对数量为$S'_{c_i}$ 其符合条件

题目描述 在Bytemountains有N座山峰,每座山峰有他的高度h_i.有些山峰之间有双向道路相连,共M条路径,每条路径有一个困难值,这个值越大表示越难走,现在有Q组询问,每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰,如果无解输出-1. 输入 第一行三个数N,M,Q.第二行N个数,第i个数为h_i接下来M行,每行3个数a b c,表示从a到b有一条困难值为c的双向路径.接下来Q行,每行三个数v x k,表示一组询问. 输出 对于每组询问,输出一个整数表示答案

Description 有一棵点数为 N 的树,以点 1 为根,且树点有边权.然后有 M 个 操作,分为三种: 操作 1 :把某个节点 x 的点权增加 a . 操作 2 :把某个节点 x 为根的子树中所有点的点权都增加 a . 操作 3 :询问某个节点 x 到根的路径中所有点的点权和. Input 第一行包含两个整数 N, M .表示点数和操作数.接下来一行 N 个整数,表示树中节点的初始权值.接下来 N-1  行每行三个正整数 fr, to , 表示该树中存在一条边 (fr, to) .再接下

这几年考了好几次树上问题: NOIP2012 疫情控制(二分答案+倍增+贪心) NOIP2013 货车运输(最大生成树+倍增) NOIP2014 联合权值(勉强算作树形dp的傻逼题) NOIP2015 运输计划(二分答案+树上差分+最近公共祖先) NOIP2016 天天爱跑步(树上差分+树上倍增) 可以说除了联合权值外都有一定的难度,(关键是我不抄题解一道也做不出来) 去年没考树上的问题所以我感觉今年要考 树 树是一种极其优美的结构,树上两点之间有且仅有一条路径. 在近年来oi中常出现关于树的题

题目的大概意思现在有一棵树,在树上找半径小于等于2的最小覆盖点的最小个数. 题目链接 讲一讲此类题的贪心策略: 就是每次寻找最低没有被覆盖的点,显然对于覆盖它的所有点中,在他的祖先处设立一个点最优.所以在它的祖先处设一个点,然后ans++,并且更新它父节点和祖先对于点的距离. 然后如果半径更大的话,需要维护的就稍微多一些,要维护到上面的k位祖先,然后其他思路一致. #include<cstdio> #include<algorithm> #include<cstring>