BZOJ4719 [Noip2016]天天爱跑步
本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。 本文作者：ljh2000作者博客：http://www.cnblogs.com/ljh2000-jump/转载请注明出处，侵权必究，保留最终解释权！ Description小c同学认为跑步非常有趣,于是决...
【NOIP2016提高组复赛】天天爱跑步
Description Solution 这道题是NOIP里面最难的一道题。 暴力打的好可以拿80分，比赛的时候还是打暴力比较好。 我们思考一下从x到y的路径，这个可以拆成从x到lca的路径和从lca到y的路径，这个很明显。 如果一个点i在从x到lca 的路径可以检测到的话，那么就有de...
洛谷P1600 天天爱跑步
天天放毒...首先介绍一个树上差分。每次进入的时候记录贡献，跟出来的时候的差值就是子树贡献。然后就可以做了。发现考虑每个人的贡献有困难。于是考虑每个观察员的答案。把路径拆成两条，以lca分开。x -> z -> y，完全分成A，B两部分。那么A：d[x] = w[z] + d[z];B：...
Noip 2016 天天爱跑步 【树上倍增+深搜】
题目： 小c同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。«天天爱跑步»是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。 这个游戏的地图可以看作一一棵包含 个结点和 条边的树, 每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从到的连续正整数。 现在...
bzoj 4719: [Noip2016]天天爱跑步
Description小c同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。?天天爱跑步?是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。这个游戏的地图可以看作一一棵包含 N个结点和N-1 条边的树, 每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从1到N...
【NOIP2016】天天爱跑步
题目描述小c同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。«天天爱跑步»是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。这个游戏的地图可以看作一一棵包含 个结点和 条边的树, 每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从到的连续正整数。现在有个玩家...
[NOIp2016]天天爱跑步 线段树合并
[NOIp2016]天天爱跑步LG传送门对于一个人，他的路程会分为两段，一段向上（根），一段向下，考虑在向上过程中他能产生贡献的观察者具有什么性质：设出发点深度为\(dep[x]\)，观察者深度为\(dep[y]\)，观察的时间为\(t\)，需满足\(dep[x] - dep[y] = t\)，换句...
【NOIP2016 Day1 T2】天天爱跑步
题目传送门：https://www.luogu.org/problemnew/show/P1600感觉这两天在处理边界问题上有点神志不清......为了从80的暴力变成100，花了整整一个下午+一个晚上的时间(还好最后还是搞了出来)题目大意：给你一棵树N个点的无根树，有M个人要从Si走到Ti,行走速...
洛谷P1600 天天爱跑步(差分 LCA 桶)
题意题目链接Sol一步一步的来考虑\(25 \%\)：直接\(O(nm)\)的暴力链的情况：维护两个差分数组，分别表示从左向右和从右向左的贡献，\(S_i = 1\)：统计每个点的子树内有多少起点即可\(T_i = 1\)：同样还是差分的思想，由于每个点 能对其产生的点的深度是相同的(假设为\(x\...
LG1600 天天爱跑步
题意分析对一个(s,t)查询，令f=lca(s,t)，则操作可化为(s,f),(f,t)。考虑观察到的情况，若x在s到t的路径上，且x观察到，则\[\textrm{dep}_s-\textrm{dep}_x=w_x\\\textrm{dep}_s=\textrm{dep}_x+w_x\]或者\[\t...
noip2016天天爱跑步
题目描述小c同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。«天天爱跑步»是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。这个游戏的地图可以看作一一棵包含 个结点和 条边的树, 每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从到的连续正整数。现在有个玩家...