不是很懂为什么luogu标签是树形DP,感觉我想的就是一个贪心啊。。。

随机造几组数据,我们发现贪心的确可以得到最优解,那么为什么呢?

假设将所有时态贪心的调整是对的,
那么如果一个节点的各个儿子时态不同,那么强行统一,
为什么可以假设是对的?
因为观察到在一个点的上方+1,对它的子树的相对关系的没有影响的,
因此子树里面的时态同步只能在内部做,所以一步一步统一上来,
而且由于如果是要改变两个子树之间的大小关系的话,
因为是整个子树的修改,同时不影响到其他子树,因此这个时候就是在一个点的上方+1了,
同时因为每次只考虑子树内部的关系,所以整个子树的修改会被延后到上一个节点,
这时两个子树之间的修改就变成了子树内部的修改,因此递归上去即可

注意:由于f[x]中存的子树个数在不断增加,因此f[x]中的个数可能不只一个,因此如果要把f[x]中的子树增加到f[now]代表的子树的话,

因为路径不同,因此要修改cnt(f[x]中的子树个数)条路径,并且每条路径都是+相同的数,所以代价要*cnt

 #include<bits/stdc++.h>
using namespace std;
/*假设将所有时态贪心的调整是对的,
那么如果一个节点的各个儿子时态不同,那么强行统一,
为什么可以假设是对的?
因为观察到在一个点的上方+1,对它的子树的相对关系的没有影响的,
因此子树里面的时态同步只能在内部做,所以一步一步统一上来,
而且由于如果是要改变两个子树之间的大小关系的话,
因为是整个子树的修改,同时不影响到其他子树,因此这个时候就是在一个点的上方+1了,
同时因为每次只考虑子树内部的关系,所以整个子树的修改会被延后到上一个节点,
这时两个子树之间的修改就变成了子树内部的修改*/
#define R register int
#define AC 1001000
#define D printf("line in %d\n",__LINE__);
#define LL long long
int n,root;
int date[AC],Next[AC],Head[AC],value[AC],tot;
LL ans,have;
LL f[AC];//f[i]代表节点i的子树内的时态已经被统一为了f[i]
bool z[AC],vis[AC];
inline int read()
{
int x=;char c=getchar();
while(c > '' || c < '') c=getchar();
while(c >= '' && c <= '') x=x*+c-'',c=getchar();
return x;
} inline void add(int f,int w,int S)
{
date[++tot]=w,Next[tot]=Head[f],value[tot]=S,Head[f]=tot;
date[++tot]=f,Next[tot]=Head[w],value[tot]=S,Head[w]=tot;
} inline void pre()
{
R a,b,c;
n=read(),root=read();
for(R i=;i<n;i++)
{
a=read(),b=read(),c=read();
add(a,b,c);
}
} void DFS(int x)//先统计一下
{
vis[x]=true;
R now;
bool done=false;
for(R i=Head[x]; i ;i=Next[i])
{
now=date[i];
if(vis[now]) continue;
if(!done) done=true;
have+=value[i];
DFS(now);
have-=value[i];
}
if(!done) f[x]=have;
} void DP(int x)
{
z[x]=true;
R now,cnt=;
for(R i=Head[x]; i ;i=Next[i])
{
now=date[i];
if(z[now]) continue;
DP(now);
if(!f[x]) f[x]=f[now];
else if(f[now] != f[x])
{
if(f[now] < f[x]) ans+=f[x] - f[now];
else ans+=(f[now] - f[x]) * cnt,f[x]=f[now];
}//error!!!因为f[now]只代表新遍历到的子树,而f[x]则可能代表很多个子树
++cnt;
}//error!!!于是如果统计让很多个子树暴力修改上来的代价,因为要修改很多边,因此要*cnt(f[x]中的子树个数)
} int main()
{
freopen("in.in","r",stdin);
pre();
DFS(root);
DP(root);
printf("%lld\n",ans);
fclose(stdin);
return ;
}
05-21 19:51