@OceanEye6年前
03/17
09:21
BZOJ1060
回来水水 文化课选手为了保持手感回来刷水题了
水题+1
大概dfs一下
在每个点上贪心的把边补齐即可
看代码吧
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <vector> #define ll long long #define p(x) ('0'<=x&&x<='9') char cc; template <class T> void read(T &x) { x=0; cc=getchar(); while(!p(cc)) cc=getchar(); while(p(cc)) { x=x*10+cc-'0'; cc=getchar(); } } #undef p using namespace std; #define N 500010 int n,pt; int fst[N],nxt[N<<1],val[N<<1],to[N<<1],etot; ll dis[N],ans; void add_e(int a,int b,int c) { val[etot]=c; to[etot]=b; nxt[etot]=fst[a]; fst[a]=etot++; val[etot]=c; to[etot]=a; nxt[etot]=fst[b]; fst[b]=etot++; } void dfs_solve(int x,int fa) { ll len; int cnt=0; for(int i=fst[x];~i;i=nxt[i]) { if(to[i]==fa) continue; ++cnt; dfs_solve(to[i],x); len=dis[to[i]]+val[i]; if(!dis[x]) { dis[x]=len; continue; } if(dis[x]>len) ans+=dis[x]-len; else ans+=(ll)(len-dis[x])*(cnt-1),dis[x]=len; } } int main() { int a,b,c; read(n); read(pt); memset(fst,-1,sizeof(fst)); for(int i=1;i<n;++i) { read(a); read(b); read(c); add_e(a,b,c); } dfs_solve(pt,0); printf("%lld",ans); return 0; } |