09年漆子超论文第二题。
主要是在算经过某一棵树的根的答案这一步很难想。假设这个根节点为u，有若干个子树v。f[i]表示已经当前要算的子树之前所有子树里面，最多经过i个黑点的最长路径是多少。这样的话，也就不难想出状态转移了。
细节有点多。。。。做得泪流满面
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#define ll int
#define lson l , m , rt << 1
#define rson m + 1 , rt << 1 | 1
#define new_edge(a,b,c) edge[tot].t = b , edge[tot].v = c , edge[tot].next = head[a] , head[a] = tot ++
using namespace std;
const int maxn = 222222 ;
const int INF = -1111111111 ;
struct Edge {
int t , next ;
ll v ;
} edge[maxn<<1] ;
int head[maxn] , vis[maxn] , tot , k ;
int mark[maxn] ;
int temp , mdp[maxn] , dp[maxn] ;
ll que[maxn] , tail , ans , dis[maxn] , f[maxn] ;
int dep[maxn] , pos[maxn] ;
int cmp ( int a , int b ) {
return dep[a] < dep[b] ;
}
int cnt_son ( int u , int fa ) {
int i ;
mdp[u] = dp[u] = 0 ;
que[++tail] = u ;
for ( i = head[u] ; i != -1 ; i = edge[i].next ) {
int e = edge[i].t ;
if ( e == fa || vis[e] ) continue ;
cnt_son ( e , u ) ;
dp[u] += dp[e] , mdp[u] = max ( mdp[u] , dp[e] ) ;
}
return ++ dp[u] ;
}
int get ( int u ) {
int temp = maxn , ret ;
tail = 0 ;
cnt_son ( u , u ) ;
while ( tail ) {
int e = que[tail--] ;
int fuck = max ( mdp[e] , dp[u] - dp[e] ) ;
if ( fuck < temp ) temp = fuck , ret = e ;
}
return ret ;
}
void get_dep ( int u , int fa , int rt , int tot ) {
int i ;
dep[u] = mark[u] ;
for ( i = head[u] ; i != -1 ; i = edge[i].next ) {
int e = edge[i].t ;
if ( e == fa || vis[e] ) continue ;
get_dep ( e , u , rt , tot + mark[e] ) ;
dep[u] = max ( dep[u] , dep[e] + mark[e] ) ;
}
}
int lim ;
ll g[maxn] ;
void gao ( int u , int fa , int x , ll len , int rt ) {
int i , j ;
if ( x + mark[rt] <= k ) {
g[x] = max ( g[x] , len ) ;
ans = max ( ans , len + f[min(k-x-mark[rt],lim)] ) ;
}
for ( i = head[u] ; i != -1 ; i = edge[i].next ) {
int e = edge[i].t ;
if ( e == fa || vis[e] ) continue ;
gao ( e , u , x + mark[e] , len + edge[i].v , rt ) ;
}
}
void dfs ( int u ) {
int cg = get ( u ) , i , j ;
u = cg ;
vis[u] = 1 ;
tail = 0 ;
for ( i = head[u] ; i != -1 ; i = edge[i].next ) {
int e = edge[i].t ;
if ( vis[e] ) continue ;
pos[e] = edge[i].v ;
que[++tail] = e ;
get_dep ( e , e , e , mark[e] ) ;
}
sort ( que + 1 , que + tail + 1 , cmp ) ;
for ( i = 0 ; i <= dep[que[tail]] ; i ++ ) f[i] = INF ;
lim = 0 ;
for ( i = 1 ; i <= tail ; i ++ ) {
for ( j = 0 ; j <= dep[que[i]] ; j ++ ) g[j] = INF ;
gao ( que[i] , que[i] , mark[que[i]] , pos[que[i]] , u ) ;
lim = dep[que[i]] ;
for ( j = 0 ; j <= dep[que[i]] ; j ++ ) {
f[j] = max ( f[j] , g[j] ) ;
if ( j ) f[j] = max ( f[j] , f[j-1] ) ;
if ( i == 1 && j + mark[u] <= k ) ans = max ( ans , f[j] ) ;
}
}
for ( i = head[u] ; i != -1 ; i = edge[i].next )
if ( !vis[edge[i].t] ) dfs ( edge[i].t ) ;
}
void init () {
memset ( head , -1 , sizeof ( head ) ) ;
memset ( vis , 0 , sizeof ( vis ) ) ;
memset ( mark , 0 , sizeof ( mark ) ) ;
memset ( f , 0 , sizeof ( f ) ) ;
tot = ans = 0 ;
}
int main() {
// freopen("E:/codeblock/test/a.txt","r",stdin);
// freopen("E:/codeblock/test/b.txt","w",stdout);
int n , i , j , m ;
while (scanf ( "%d%d%d" , &n , &k , &m ) != EOF ) {
init () ;
ans = 0 ;
int a , b , c ;
for ( i = 1 ; i <= m ; i ++ ) {
scanf ( "%d" , &a ) ;
mark[a] = 1 ;
}
for ( i = 1 ; i < n ; i ++ ) {
scanf ( "%d%d%d" , &a , &b , &c ) ;
new_edge ( a , b , c ) ;
new_edge ( b , a , c ) ;
}
dfs ( 1 ) ;
printf ( "%d\n" , ans ) ;
}
return 0;
}
/*
8 2 3
3
5
7
1 3 1
2 3 10
3 4 -2
4 5 -1
5 7 6
5 6 5
4 8 3
9 3 4
2
4
6
5
5 1 -5
8 9 5
9 5 2
2 4 -1
9 2 2
4 7 9
3 2 -4
6 9 6
6 3 5
1
5
3
6
2
5 2 8
3 4 3
6 4 8
3 2 7
3 1 2
10 1 3
6
8
1
9 4 -8
6 9 -9
2 9 -3
3 8 8
3 6 8
5 9 8
2 10 -2
4 1 8
8 7 -2
*/