正文

luogup1131时态同步(代码片段)

yuyanjiab  yuyanjiab  2023-01-15  430

关键词：

题面贼长题贼简单

修改边权使得所有叶子结点到根的路径长度相同

dfs的时候回溯修改成最大值即可

Code:

 1 // luogu-judger-enable-o2
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cstring>
 6 #define inf 2147483647
 7 #define rep(i,a,n) for(int i = a;i <= n;i++)
 8 #define per(i,n,a) for(int i = n;i >= a;i--)
 9 using namespace std;
10 typedef long long ll;
11 int read() 
12     int as = 0,fu = 1;
13     char c = getchar();
14     while(c<‘0‘||c>‘9‘) 
15         if(c == ‘-‘) fu = -1;
16         c = getchar();
17     
18     while(c<=‘9‘&&c>=‘0‘) 
19         as = as * 10 + c - ‘0‘;
20         c = getchar();
21     
22     return as * fu;
23 
24 const int N = 1000005;
25 //head
26 int n,s;
27 int head[N],nxt[N],mo[N],cnt;
28 ll cst[N],stk[N],top,sum;
29 inline void add(int x,int y,ll z) 
30   mo[++cnt] = y;
31   cst[cnt] = z;
32   nxt[cnt] = head[x];
33   head[x] = cnt;
34   return;
35 
36 ll dep[N];
37 
38 int dfs(int x,int f) 
39   for(int i = head[x];i;i = nxt[i]) 
40     int sn = mo[i];
41     if(sn == f)continue;
42     dfs(sn,x);
43     dep[x] = max(dep[sn] + cst[i],dep[x]);
44   
45   for(int i = head[x];i;i = nxt[i]) 
46     int sn = mo[i];
47     if(sn == f) continue;
48     sum += dep[x] - dep[sn] - cst[i];
49   
50   return dep[x];
51 
52 
53 
54 int main() 
55   n = read();
56   s = read();
57   rep(i,1,n-1) 
58     int x = read();
59     int y = read();
60     ll z = read();
61     add(x,y,z);
62     add(y,x,z);
63   
64   dfs(s,s);
65   printf("%lld
",sum);
66   return 0;
67

[bzoj1060][luogup1131]时态同步

(似乎是)第一次做树形DP吔,好鸡冻~ 题目大意:一棵有根边权树,修改边权值代价为边权值变化量,目标状态是每个叶子到根的路径权值相等.求达到目标状态耗费的最小代价. 要把每条路径的权值加到最大权值,可以证... 查看详情

[luogup1131][zjoi2007]时态同步（贪心）

传送门显然是一棵树。又显然一段一段地增加比较优。我们可以dfs，并且尽量把每一个节点所有子树中所有节点的时间增加到一样。 #include<vector>#include<cstdio>#include<cstring>#include<iostream>#defineN500001#defineLL... 查看详情

p1131[zjoi2007]时态同步（树形dp）(代码片段)

P1131[ZJOI2007]时态同步设$f[i]$为与$i$与最远的点的距离在dfs时每次更新的时候顺便统计一下长度，不同的话就改成最长的那条并更新答案#include<iostream>#include<cstdio>#include<cstring>#include<cctype>#definereregisterusingnamespaces 查看详情

p1131[zjoi2007]时态同步(代码片段)

P1131[ZJOI2007]时态同步题意：有一颗树，有一个点是激发器，从这个点开始可以产生一个激励电流，通过导线传向每一个它所连接的节点，经过一个边的花费为w[i],你有一个道具，每用一次可以让一个边的花... 查看详情

p1131[zjoi2007]时态同步(代码片段)

$\colorcyan>>Question$题意让我们用最少的代价把叶子节点到根节点的距离调成相同每次向最长链看齐即可令$f[u]$表示以$u$为根到叶节点的最长链长度则$$f[u]=max\left\f[v]+e(u,v)\right\$$统计答案$$ans=\sum_v(e(u,v)\inE)f[u]-(f[v]+e(u,v))$$上代码... 查看详情

p1131[zjoi2007]时态同步树形dp(代码片段)

　　题目描述小QQ在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3…1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两... 查看详情

p1131[zjoi2007]时态同步(代码片段)

P1131[ZJOI2007]时态同步树形DP题意描述有一棵树，有n个节点，n-1条边，每条边都有一个权值。要求每个叶子结点到根节点的边权相同，求最少的改动数量（不是次数）看不懂的话，走传送门算法分析很显然是DP（我也不知道是怎么... 查看详情

zjoi/lnsyoj158/luogu1131时态同步（树形dp水题）做题报告(代码片段)

rt，是一道很水的树形DP题目描述给出一棵有根树，每条边有一个通过时间。你可以进行一次“操作”，使得某条边的通过时间增加一秒。你需要让根节点到每个叶节点的所需时间都相等，且“操作”次数最少。叶节... 查看详情

p1131[zjoi2007]时态同步(代码片段)

串松门标签是树形dp，但其实没啥必要用dp。显然数据给出的是树形结构，要求所有叶子节点到根节点路径长度相同，可以想到自下向上地进行维护。首先从根节点dfs，找到叶子节点后向上回溯，先维护父节点的所有子节点到父... 查看详情

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….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板... 查看详情

洛谷p1131时态同步

做这个题还是比较顺手的，起码做起来挺舒服的。他让我们求使所有叶子节点到根节点距离一样的代价，那么作为一颗子树来说首先就要满足这点，因为再往上走的路径都是一样的，因此我们需要先求所有子树的最大深度，然后... 查看详情

洛谷1131[zjoi2007]时态同步

题目描述小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在且... 查看详情

bzoj1060：[zjoi2007]时态同步——题解(代码片段)

http://www.lydsy.com/JudgeOnline/problem.php?id=1060https://www.luogu.org/problemnew/show/P1131小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若... 查看详情

洛谷p1131[zjoi2007]时态同步

题目描述小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在... 查看详情

洛谷p1131bzoj1060[zjoi2007]时态同步

[bzoj1060]时态同步(代码片段)

1060:[ZJOI2007]时态同步TimeLimit: 10Sec MemoryLimit: 162MBDescription　　小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若... 查看详情