Submission #537695

#	Time	Username	Problem	Language	Result	Execution time	Memory
537695		zaneyu	Paths (RMI21_paths)	C++14	31 / 100	889 ms	18568 KiB

Main

/*input
11 1
1 2 5
2 3 3
2 6 5
3 4 4
3 5 2
1 7 6
7 8 4
7 9 5
1 10 1
10 11 1
*/
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define MNTO(x,y) x=min(x,y)
#define MXTO(x,y) x=max(x,y)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define ld long double
#define sz(x) (int)x.size()
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
const int maxn=1e5+5;
vector<pii> v[maxn];
ll dp[1005][1005];
int dep[maxn];
ll dist[maxn];
int k;
int par[maxn][20];
int dfs(int u,int p){
    
    int s=(sz(v[u])==1);
    for(auto x:v[u]){
        if(x.f==p) continue;
        s+=dfs(x.f,u);
        for(int j=min(s,k);j>=0;j--){
            REP1(z,min(s,k)-j){
                MXTO(dp[u][j+z],dp[u][j]+dp[x.f][z]+x.s);
                if(!dp[x.f][z]) break;
            }
        }
    }
    return s;
}
void dfs2(int u,int p){
    par[u][0]=p;
    for(auto x:v[u]){
        if(x.f==p) continue;
        dep[x.f]=dep[u]+1;
        dist[x.f]=dist[u]+x.s;
        dfs2(x.f,u);
    }
}
ll d2[maxn];
void dfs3(int u,int p){
    for(auto x:v[u]){
        if(x.f==p) continue;
        d2[x.f]=d2[u]+x.s;
        dfs3(x.f,u);
    } 
}
#define lowb(x) x&(-x)
int lca(int a,int b){
    if(dep[a]<dep[b]) swap(a,b);
    int d=dep[a]-dep[b];
    while(d){
        int z=__lg(lowb(d));
        a=par[a][z];
        d-=lowb(d);
    }
    if(a==b) return a;
    for(int j=19;j>=0;j--){
        if(par[a][j]!=par[b][j]){
            a=par[a][j],b=par[b][j];
        }
    }
    return par[a][0];
}
ll get(int a,int b){
    return dist[a]+dist[b]-2*dist[lca(a,b)];
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n;
    cin>>n>>k;
    REP(i,n-1){
        int a,b,c;
        cin>>a>>b>>c;
        --a,--b;
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
    if(k==1){
        dfs2(0,-1);
        REP1(j,19){
            REP(i,n){
                if(par[i][j-1]!=-1) par[i][j]=par[par[i][j-1]][j-1];
                else par[i][j]=-1;
            }
        }
        dfs3(0,-1);
        int p=max_element(d2,d2+n)-d2;
        int a=p;
        d2[p]=0;
        dfs3(p,-1);
        p=max_element(d2,d2+n)-d2;
        REP(i,n){
            cout<<max(get(i,p),get(i,a))<<'\n';
        }
        return 0;
    }
    dfs(0,-1);
    REP(i,n){
        REP(j,n) REP(a,k+1) dp[j][a]=0;
        dfs(i,-1);
        cout<<dp[i][k]<<'\n';
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 12 / 12
• Subtask 6: 0 / 32