348E - Pilgrims - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp              make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("connect.in" , "r" , stdin) ; freopen("connect.out" , "w" , stdout);

ll mod = 1e9+7 ;

const int N = 1e5+23, L=23;
const int INF=1e9+23;

pll dpd[N], dpu[N], dp[N];
ll ans[N];
int is[N];
vector<pll> g[N];
int h[N], par[N][L];
int n, m;


void dfs1(int v, int p=0){//LCA dpd
    if(is[v]) dpd[v]={0, v};
    for (auto pp: g[v]){
        int u=pp.F, w=pp.S;
        if(u==p) continue;
        par[u][0]=v;
        h[u]=h[v]+1;
        dfs1(u, v);
        if(dpd[u].F+w>dpd[v].F)dpd[v]={dpd[u].F+w, dpd[u].S};
        else if(dpd[u].F+w==dpd[v].F) dpd[v].S=v;

    }
}

void dfs2(int v, int p=0){//dpu dp
    if(dpu[v].F<0 && is[v]) dpu[v]={0, v};
    vector<pll> vec;
    for (auto pp : g[v]){
        int u=pp.F, w=pp.S;
        if(u==p) continue;
        vec.pb({dpd[u].F+w, dpd[u].S});
    }
    vec.pb(dpu[v]);
    sort(all(vec));
    int num=0;
    int Mx=vec.back().F;
    for (auto pp: vec) if(pp.F==Mx) num++;
    int nnum=0;
    if(vec.size()>=2){
        int Mxx=vec[vec.size()-2].F;
        for (auto pp: vec) if(pp.F==Mxx) nnum++;
        if(Mxx==Mx) nnum=num-1;
    }

    for (auto pp : g[v]){
        int u=pp.F, w=pp.S;
        if(u==p) continue;
        pll temp=dpd[u];
        temp.F+=w;
        if(temp==vec.back())dpu[u]=vec[vec.size()-2];
        else dpu[u]=vec.back();
        dpu[u].F+=w;
        if(temp.F<Mx && num>1)dpu[u].S=v;
        if(temp.F==Mx && nnum>1) dpu[u].S=v;
    }
    for (auto pp : g[v]){
        int u=pp.F, w=pp.S;
        if(u==p) continue;
        dfs2(u, v);
    }

    if(dpd[v].F>dpu[v].F) dp[v]=dpd[v];
    if(dpu[v].F>dpd[v].F) dp[v]=dpu[v];
    if(dpu[v].F==dpd[v].F) dp[v]={dpd[v].F, v};

}

void dfs3(int v, int p=0){//ans

    for (auto pp : g[v]){
        int u=pp.F, w=pp.S;
        if(u==p) continue;
        dfs3(u, v);
        ans[v]+=ans[u];
    }
}

int LCA(int v, int u){
    if(h[v]>h[u]) swap(u, v);
    int d=h[u]-h[v];
    for (int i=0; i<L; i++) if(d>>i&1) u=par[u][i];
    if(u==v) return v;
    for (int i=L-1; i>=0; i--){
        if(par[u][i]!=par[v][i]){
            u=par[u][i];
            v=par[v][i];
        }
    }
    return par[v][0];
}

int main()
{
    fast_io
    cin>>n>>m;
    for (int i=0; i<m; i++){
        int v; cin>>v;
        is[v]=1;
    }
    for (int i=1; i<=n; i++)dpd[i].F=dpu[i].F=-INF;
    for (int i=0; i<n-1; i++){
        int u, v, w; cin>>v>>u>>w;
        g[v].pb({u, w}); g[u].pb({v, w});
    }
    dfs1(1);
    for (int j=1; j<L; j++) for (int i=1; i<=n; i++) par[i][j]=par[par[i][j-1]][j-1];
    dfs2(1);
    for (int i=1; i<=n; i++){
        if(!is[i]) continue;
        int lca=LCA(i, dp[i].S);
        ans[i]++;
        ans[dp[i].S]++;
        ans[lca]--;
        ans[par[lca][0]]--;
    }
    dfs3(1);
    ll res=-1, num=0;
    for (int i=1; i<=n; i++) {
        if(!is[i] && ans[i]>res){
            res=ans[i];
            num=1;
        }
        else if(!is[i] && ans[i]==res)num++;
    }
    cout<<res<<" "<<num<<endl;

}