CFR 701 E. Connecting Universities ( Graph )

Problem - E - Codeforces
Consider rooting the tree with 1 as root. DFS down, and observe each edge, the number of towns that are below the edge, and above the edge ( 2 * K - below_edge_cnt ). We will know that the maximum number of pairs should go through each edge. Therefore, the number that this edge will be passed as part of the route, is min( below_edge_town_cnt, 2 * K - below_edge_town_cnt ). Examine for each edge and sum up.
The key is to consider each edge, how many times will it be counted, instead of considering each town.

int N, K;
vi is_town;
vvi G;

vi town_in_subtree;
void dfs( int u, int fa, ll &ans ){
    if( is_town[ u ] )
        ++town_in_subtree[ u ];

    for( int v : G[ u ] ){
        if( v == fa ) continue;
        dfs( v, u, ans );
        town_in_subtree[ u ] += town_in_subtree[ v ];
        ans += min( 2 * K - town_in_subtree[ v ], town_in_subtree[ v ] );
    }
}

void solve(){
    cin >> N >> K;
    is_town = vi( N );
    G = vvi( N );
    town_in_subtree = vi( N );
    for( int i = 0; i < K * 2; ++i ){
        int u; cin >> u;
        is_town[ u - 1 ] = 1;
    }
    for( int i = 0; i < N - 1; ++i ){
        int u, v; cin >> u >> v;
        G[ u - 1 ].push_back( v - 1 );
        G[ v - 1 ].push_back( u - 1 );
    }

    ll ans = 0;
    dfs( 0, -1, ans );

    cout << ans << "\n";
}