2 条题解
-
1
WiFi LV 8 @ 6 年前
-
04 年前@
- 1
信息
- 难度
- 4
- 分类
- (无)
- 标签
- 递交数
- 48
- 已通过
- 22
- 通过率
- 46%
- 被复制
- 2
- 上传者
#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]);
}
#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;
}