BZOJ 1060
orzzyy 跪烂
如果要满足题目的要求，则以每一个非叶节点 到其子树中所有叶子节点距离相同
这很显然
然后考虑到我们只能加大一条边的权值而不能减小
所以我们只能所有路径加长到最长的那一条
所以我们只要贪心就好了
具体实现看代码
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <queue> #include <string> #include <map> #include <set> #include <cstring> #include <ctime> #include <vector> #define inf 1e9 #define eps 1e-9 #define iter multiset<ll>::iterator #define ll long long #define maxn 20010 #define For(i,j,k) for(ll i=j;i<=k;i++) #define Dow(i,j,k) for(ll i=k;i>=j;i--) using namespace std; inline void read(ll &tx){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} tx=x*f; } inline void write(ll x){ if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x+'0'); } inline void writeln(ll x){write(x);puts("");} ll f[1000001],poi[1000001],nxt[1000001],v[1000001],cnt,mx[1000001],n,s,x,y,z; ll ans; inline void add(ll x,ll y,ll z){poi[++cnt]=y;nxt[cnt]=f[x];v[cnt]=z;f[x]=cnt;} inline void dfs(ll x,ll fa) { for(ll i=f[x];i;i=nxt[i]) { if(poi[i]==fa) continue; dfs(poi[i],x); mx[x]=max(mx[x],mx[poi[i]]+v[i]); } for(ll i=f[x];i;i=nxt[i]) { if(poi[i]==fa) continue; ans+=(ll)(mx[x]-mx[poi[i]]-v[i]); } } int main() { read(n);read(s); For(i,1,n-1) { read(x);read(y);read(z); add(x,y,z);add(y,x,z); } dfs(s,0); writeln(ans); }
