关键词：
http://www.lydsy.com/JudgeOnline/problem.php?id=1060
https://www.luogu.org/problemnew/show/P1131
小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在且仅存在一条通路（通路指连接两个元件的导线序列）。
在电路板上存在一个特殊的元件称为“激发器”。当激发器工作后，产生一个激励电流，通过导线传向每一个它所连接的节点。而中间节点接收到激励电流后，得到信息，并将该激励电流传向与它连接并且尚未接收到激励电流的节点。最终，激烈电流将到达一些“终止节点”――接收激励电流之后不再转发的节点。
激励电流在导线上的传播是需要花费时间的，对于每条边e，激励电流通过它需要的时间为te，而节点接收到激励电流后的转发可以认为是在瞬间完成的。现在这块电路板要求每一个“终止节点”同时得到激励电路――即保持时态同步。由于当前的构造并不符合时态同步的要求，故需要通过改变连接线的构造。目前小Q有一个道具，使用一次该道具，可以使得激励电流通过某条连接导线的时间增加一个单位。请问小Q最少使用多少次道具才可使得所有的“终止节点”时态同步？
题面很长，看完就知道是树上dp裸题且很简单。
（然后我就傻了少加了很多东西）
显然对于给定的一个节点，其子树上的最晚时间即是最优时间。
所以维护dp[i][0]为i节点往下传的最晚时间，dp[i][1]为i的子树用了多少道具。
所以我们有
dp[u][1]+=dp[u][0]-dp[v][0]-w+dp[v][1];
很显然吧。
（然而请一定提前更新最晚时间，不要边找最大值边更新dp1不然你就会像我一样卡在sb题上。）
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=5e5+5; inline int read() int X=0,w=0;char ch=0; while(!isdigit(ch))w|=ch==\'-\';ch=getchar(); while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; struct node int to,nxt; ll w; e[N*2]; int n,rt,cnt,head[N]; ll dp[N][2]; inline void add(int u,int v,ll w) e[++cnt].to=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt; void dfs(int u,int f) for(int i=head[u];i;i=e[i].nxt) int v=e[i].to;ll w=e[i].w; if(v==f)continue; dfs(v,u); dp[u][0]=max(dp[u][0],dp[v][0]+w); for(int i=head[u];i;i=e[i].nxt) int v=e[i].to;ll w=e[i].w; if(v==f)continue; dp[u][1]+=dp[u][0]-dp[v][0]-w+dp[v][1]; int main() n=read();rt=read(); for(int i=1;i<n;i++) int u=read(),v=read(),w=read(); add(u,v,w);add(v,u,w); dfs(rt,0); printf("%lld\\n",dp[rt][1]); return 0;
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++
bzoj千题计划163：bzoj1060:[zjoi2007]时态同步
http://www.lydsy.com/JudgeOnline/problem.php?id=1060 以激发器所在节点为根终止节点一定是叶节点记录点的子树内最深的终止节点然后从根往下使用道具道具的使用次数为整棵树最深的叶子节点深度-本节点子树内最深的叶子节点深度-本... 查看详情
bzoj1060[zjoi2007]时态同步(代码片段)
传送门Description 小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，... 查看详情
bzoj1060:[zjoi2007]时态同步树形dp(代码片段)
可能算不上dp，大概是个树形模拟先一遍dfs算出f[u]为每个点最深的叶子到u的距离，然后再dfs一下，ans加上f[u]-f[e[i].to]-e[i].va，f[u]-f[e[i].to]是这条边应该的用时#include<iostream>#include<cstdio>usingnamespacestd;constintN=500005;intn,m,cnt,f... 查看详情
洛谷p1131bzoj1060[zjoi2007]时态同步
题目描述小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在... 查看详情
bzoj10601060:[zjoi2007]时态同步（树形dp）
1060:[ZJOI2007]时态同步Description 小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任... 查看详情
1060:[zjoi2007]时态同步(代码片段)
TimeLimit: 10Sec MemoryLimit: 162MBSubmit: 3610 Solved: 1521[Submit][Status][Discuss]Description 小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3&helli 查看详情
[bzoj1060]时态同步(代码片段)
1060:[ZJOI2007]时态同步TimeLimit: 10Sec MemoryLimit: 162MBDescription 小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若... 查看详情
[zjoi2007]时态同步
1060:[ZJOI2007]时态同步TimeLimit:10Sec MemoryLimit:162MBSubmit:2629 Solved:880[Submit][Status][Discuss]Description 小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….... 查看详情
b1060[zjoi2007]时态同步dfs(代码片段)
两遍dfs，第一遍有点像找重链，第二遍维护答案，每个点维护一个当前深度，然后就没啥了。ps:memset(lst,-1,sizeof(lst));这一句多余的话让我debug半天。。。题干：Description 小Q在电子工艺实习课上学习焊接电路板。一块电路板由... 查看详情
[zjoi2007]时态同步
1060:[ZJOI2007]时态同步2017-09-10Description 小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电... 查看详情
每日总结
...OI2007]矩阵游戏，挺水的二分图。看了一眼[bzoj1060][ZJOI2007]时态同步觉得挺水的就写了。 查看详情
bzoj1060时态同步
贪心。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#definemaxv500500#definemaxe1000500usingnamespacestd;intn,s,x,y,z,f[maxv],g[maxv],nume=1;longlongans=0; 查看详情
bzoj_1060_时态同步_树形dp
BZOJ_1060_时态同步_树形DP题意：http://www.lydsy.com/JudgeOnline/problem.php?id=1060分析：水水的树形DP。用儿子的最大值更新父亲，边更新边累加ans。代码：#include<stdio.h>#include<string.h>#include<algorithm>usingnamespacestd; 查看详情
[zjoi2007]时态同步
寒假填坑五十道省选题——第二道[ZJOI2007]时态同步 题目描述小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由... 查看详情
bzoj1060时态同步
题目大意：一棵树，给定根节点，可以给某些边加上一些权值，每加一，答案加一求最小答案使根节点到每个叶子节点路径上的权值和相思路：树形dp对于每个节点，dp表示到该节点的所有叶子节点满足题目的最小答案转移可以... 查看详情
bzoj1060时态同步
Description 小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在... 查看详情
luogu1131[zjoi2007]时态同步
num[x]表示x到达叶子最远路径。每个子节点对答案的贡献是num[x]-(num[t]+edge[i].val)#include<iostream>#include<cstdio>usingnamespacestd;typedeflonglongll;intn,ss,hea[500005],cnt,uu,vv,ww;llnum[500005],ans;structEdge 查看详情
洛谷p1131[zjoi2007]时态同步
P1131[ZJOI2007]时态同步 题目描述小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板... 查看详情