网站建设下什么科目,wordpress全景图,哪里有网站建设培训班,长沙做网站推广哪家好problem
洛谷链接
solution
结论#xff1a;使用道具的导线深度越浅越好。
显然#xff0c;如果有两个终止节点都需要增加 xxx#xff0c;那么在他们的 lca\text{lca}lca 到根的路径中任意一条边增加 xxx 即可#xff0c;各自增加 xxx 显然不优。
所以我们不妨倒过来使用道具的导线深度越浅越好。
显然如果有两个终止节点都需要增加 xxx那么在他们的 lca\text{lca}lca 到根的路径中任意一条边增加 xxx 即可各自增加 xxx 显然不优。
所以我们不妨倒过来从叶子自底向上推根。
将问题转化为从叶子同时出发最后同时到达根的最小使用道具次数。
显然我们只会在迫不得已的时候终止节点上方有另外的终止节点出现必须马上跟上才进行道具使用。
直接魔改拓扑排序就能递推信息了。但我这个sb调了蛮久的
code
#include bits/stdc.h
using namespace std;
#define int long long
#define maxn 500005
int n, rt;
int f[maxn], len[maxn], deg[maxn];
int Max[maxn], sum[maxn], siz[maxn];
vector pair int, int G[maxn];
queue int q;void dfs( int u, int fa ) {f[u] fa;for( int i 0;i G[u].size();i ) {int v G[u][i].first, w G[u][i].second;if( v fa ) continue;else deg[u] , siz[u] , len[v] w, dfs( v, u );}
}signed main() {scanf( %lld %lld, n, rt );for( int i 1, u, v, w;i n;i ) {scanf( %lld %lld %lld, u, v, w );G[u].push_back( make_pair( v, w ) );G[v].push_back( make_pair( u, w ) );}dfs( rt, 0 );int ans 0;for( int i 1;i n;i )if( i ^ rt and G[i].size() 1 )q.push( i );while( ! q.empty() ) {#define fa f[u]int u q.front(); q.pop();//Max[u]:u子树内距离u最远的叶子节点距离//siz[u]:u子树内的叶子节点个数//sum[u]:u子树内所有叶子离u的距离和ans Max[u] * siz[u] - sum[u];Max[fa] max( Max[fa], Max[u] len[u] );sum[fa] Max[u] len[u];deg[fa] --;if( fa and ! deg[fa] ) q.push( fa );}printf( %lld\n, ans );return 0;
}
