题目描述
题目描述
小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3…进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在且仅存在一条通路（通路指连接两个元件的导线序列）。
在电路板上存在一个特殊的元件称为“激发器”。当激发器工作后，产生一个激励电流，通过导线传向每一个它所连接的节点。而中间节点接收到激励电流后，得到信息，并将该激励电流传向与它连接并且尚未接收到激励电流的节点。最终，激励电流将到达一些“终止节点”――接收激励电流之后不再转发的节点。
激励电流在导线上的传播是需要花费时间的，对于每条边e，激励电流通过它需要的时间为te，而节点接收到激励电流后的转发可以认为是在瞬间完成的。现在这块电路板要求每一个“终止节点”同时得到激励电路――即保持时态同步。由于当前的构造并不符合时态同步的要求，故需要通过改变连接线的构造。目前小Q有一个道具，使用一次该道具，可以使得激励电流通过某条连接导线的时间增加一个单位。请问小Q最少使用多少次道具才可使得所有的“终止节点”时态同步？
题目解析
树形DP吗？完全不知道为什么要用。
贪心就可以了
首先明确一个性质：
证明：
策略
既然我们要保证每个节点所有子树深度相同，我们可以贪心的处理每个点，把深度用道具强行补到相同。
在dfs的时候，把当前搜索的这个点的子树中最深的深度记为maxdeep。
之后ans += ∑(maxdeep - 这个点的其它子树的深度);
细节看代码吧
Code
#include<iostream>
#include<cstdio>
#include<cctype>
#define int long long//不开LL会66分的
using namespace std; const int MAXN = + ; struct Edge {
int nxt;
int to,w;
} l[MAXN<<]; int n,root,ans;
int head[MAXN],cnt;
int maxdeep[MAXN]; inline int rd() {
int x=,f=;char ch=getchar();
while(!isdigit(ch)) {f=(ch=='-')?-:;ch=getchar();}
while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}
return x*f;
} inline void add(int x,int y,int z) {
cnt++;
l[cnt].nxt = head[x];
l[cnt].to = y;
l[cnt].w = z;
head[x] = cnt;
return;
} void dfs(int x,int from) {
int son = maxdeep[x];//提前记一下，因为下面更新要用到原来maxdeep[x]的值，所以用son来记最大的深度
for(int i = head[x];i;i = l[i].nxt) {
if(l[i].to == from) continue;
maxdeep[l[i].to] = maxdeep[x] + l[i].w;
dfs(l[i].to,x);
son = max(son,maxdeep[l[i].to]);
}
maxdeep[x] = son;
for(int i = head[x];i;i = l[i].nxt) {
if(l[i].to == from) continue;
ans += maxdeep[x] - maxdeep[l[i].to];
}
return;
} signed main() {
scanf("%lld%lld",&n,&root);
int x,y,z;
for(register int i = ;i < n;i++) {
x = rd(), y = rd(), z = rd();
add(x,y,z), add(y,x,z);
}
dfs(root,-);
printf("%lld\n",ans);
return ;
}