2 条题解
-
1WiFi LV 8 @ 2018-08-09 01:27:30
#include<bits/stdc++.h> using namespace std; inline int read() { int x=0, w=1; char ch=0; while (ch<'0' || ch>'9') { if (ch=='-') w=-1; ch=getchar(); } while (ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0', ch=getchar(); return x*w; } inline void write(long long x) { if (x<0) putchar('-'), x=-x; if (x>9) write(x/10); putchar(x%10+'0'); } int N,S,head[500004],cnt=0,vis[500004]; long long dp[500004],f[500004]; struct node{ int to,next,w; }e[1000004]; void add(int u,int v,int w){ e[++cnt].to=v;e[cnt].next=head[u];e[cnt].w=w;head[u]=cnt; } void treedp(int root){ vis[root]=1;long long maxx=0,p=0;int num=0; for(int i=head[root];i;i=e[i].next){ int v=e[i].to,w=e[i].w; if(vis[v]) continue; treedp(v);num++; maxx=max(maxx,(long long)f[v]+w); p=(long long) p+f[v]+w; dp[root]+=dp[v]; } dp[root]=(long long)maxx*num+dp[root]-p; f[root]=maxx; } int main(){ N=read(),S=read(); for(int i=1;i<N;i++){ int x=read(),y=read(),z=read(); add(x,y,z);add(y,x,z); } treedp(S); write(dp[S]); }
-
02020-09-11 16:02:14@
#include<bits/stdc++.h> using namespace std; const int N = 500000 + 5; int n, s, head[N], cnt, maxn[N]; long long ans; struct node{ int u, v, nxt, w; }edge[N << 1]; void add(int u, int v, int val){ edge[++ cnt].u = u; edge[cnt].v = v; edge[cnt].w = val; edge[cnt].nxt = head[u]; head[u] = cnt; } void dfs(int now, int fa){ for(int i = head[now]; i; i = edge[i].nxt){ int to = edge[i].v; if(to == fa) continue; dfs(to, now); } for(int i = head[now]; i; i = edge[i].nxt){ int to = edge[i].v; if(to == fa) continue; maxn[now] = max(maxn[now], edge[i].w); } for(int i = head[now]; i; i = edge[i].nxt){ int to = edge[i].v; if(to == fa) continue; ans += (maxn[now] - edge[i].w); } for(int i = head[fa]; i; i = edge[i].nxt){ int to = edge[i].v; if(to == now) edge[i].w += maxn[now]; } } int main(){ scanf("%d %d", &n, &s); for(int i = 1, x, y, z; i < n; i ++){ scanf("%d %d %d", &x, &y, &z); add(x, y, z); add(y, x, z); } dfs(s, 0); printf("%lld\n", ans); return 0; }
- 1
信息
- 难度
- 4
- 分类
- (无)
- 标签
- 递交数
- 48
- 已通过
- 22
- 通过率
- 46%
- 被复制
- 2
- 上传者