关键词：
1060: [ZJOI2007]时态同步
Time Limit: 10 Sec Memory Limit: 162 MBDescription
Input
Output
仅包含一个整数V，为小Q最少使用的道具次数
Sample Input
1
1 2 1
1 3 3
Sample Output
HINT
N ≤ 500000，te ≤ 1000000
由题意可知读入的是一棵树,直接树形dp,比较水.
num[i]表示i的子树完成时态同步需要补成的时间长短,f[i]统计答案.
1 #include <cstdio> 2 #include <vector> 3 #include <algorithm> 4 #define ll long long 5 using namespace std; 6 struct edge 7 int v,w; 8 ; 9 ll num[500001];//i的子树均同步需要补成的时间长度 10 int n,s,x,y,t,cnt; 11 ll f[500001],maxx,ans; 12 vector<edge> ve[500001]; 13 void dfs(int x,int fa) 14 ll maxx=0; 15 for(int i=0;i<ve[x].size();i++) 16 if(ve[x][i].v!=fa) 17 dfs(ve[x][i].v,x),num[x]=max(num[x],num[ve[x][i].v]+ve[x][i].w); 18 for(int i=0;i<ve[x].size();i++) 19 if(ve[x][i].v!=fa) 20 f[x]+=f[ve[x][i].v]+num[x]-num[ve[x][i].v]-ve[x][i].w; 21 22 int main() 23 scanf("%d%d",&n,&s); 24 for(int i=1;i<n;i++) 25 scanf("%d%d%d",&x,&y,&t); 26 ve[x].push_back((edge)y,t); 27 ve[y].push_back((edge)x,t); 28 29 dfs(s,0); 30 printf("%lld ",f[s]); 31 return 0; 32
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... 查看详情
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; 查看详情
bzoj1060时态同步
贪心。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#definemaxv500500#definemaxe1000500usingnamespacestd;intn,s,x,y,z,f[maxv],g[maxv],nume=1;longlongans=0; 查看详情
[bzoj1060][luogup1131]时态同步
(似乎是)第一次做树形DP吔,好鸡冻~ 题目大意:一棵有根边权树,修改边权值代价为边权值变化量,目标状态是每个叶子到根的路径权值相等.求达到目标状态耗费的最小代价. 要把每条路径的权值加到最大权值,可以证... 查看详情
[bzoj1060][zjoi2007]时态同步树形dp
1060:[ZJOI2007]时态同步TimeLimit: 10Sec MemoryLimit: 162MBSubmit: 2988 Solved: 1086[Submit][Status][Discuss]Description 小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节 查看详情
bzoj1060时态同步
题目大意：一棵树，给定根节点，可以给某些边加上一些权值，每加一，答案加一求最小答案使根节点到每个叶子节点路径上的权值和相思路：树形dp对于每个节点，dp表示到该节点的所有叶子节点满足题目的最小答案转移可以... 查看详情
bzoj1060时态同步
Description 小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在... 查看详情
bzoj千题计划163：bzoj1060:[zjoi2007]时态同步
http://www.lydsy.com/JudgeOnline/problem.php?id=1060 以激发器所在节点为根终止节点一定是叶节点记录点的子树内最深的终止节点然后从根往下使用道具道具的使用次数为整棵树最深的叶子节点深度-本节点子树内最深的叶子节点深度-本... 查看详情
bzoj1060时态同步[树形dp]
Description小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在且仅... 查看详情
1060:[zjoi2007]时态同步(代码片段)
TimeLimit: 10Sec MemoryLimit: 162MBSubmit: 3610 Solved: 1521[Submit][Status][Discuss]Description 小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3&helli 查看详情
洛谷p1131bzoj1060[zjoi2007]时态同步
题目描述小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在... 查看详情
b1060[zjoi2007]时态同步dfs(代码片段)
两遍dfs，第一遍有点像找重链，第二遍维护答案，每个点维护一个当前深度，然后就没啥了。ps:memset(lst,-1,sizeof(lst));这一句多余的话让我debug半天。。。题干：Description 小Q在电子工艺实习课上学习焊接电路板。一块电路板由... 查看详情
bzoj10601060:[zjoi2007]时态同步（树形dp）
1060:[ZJOI2007]时态同步Description 小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任... 查看详情
[zjoi2007]时态同步
1060:[ZJOI2007]时态同步TimeLimit:10Sec MemoryLimit:162MBSubmit:2629 Solved:880[Submit][Status][Discuss]Description 小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….... 查看详情
每日总结
...OI2007]矩阵游戏，挺水的二分图。看了一眼[bzoj1060][ZJOI2007]时态同步觉得挺水的就写了。 查看详情
[zjoi2007]时态同步
1060:[ZJOI2007]时态同步2017-09-10Description 小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电... 查看详情
luogup1131时态同步(代码片段)
传送门题面贼长 题贼简单修改边权使得所有叶子结点到根的路径长度相同dfs的时候回溯修改成最大值即可Code:1//luogu-judger-enable-o22#include<cstdio>3#include<algorithm>4#include<cstring>5#include<cstring>6#defineinf21474836 查看详情