题解

2 条题解

  • 1
    @ 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]);
    }
    
  • 0
    @ 2020-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
上传者