看到没有人用老师的办法，于是自己写一下思路
思路第一步:排除旧方法
首先这道题和$4178$不一样，因为那道题是计数，而这道题是求最值，最值有个坏处，就是对于来自相同子树的信息没法高效剔除,比如容斥用不了，举例来说，对于这道题，如果我们继续用尺取法维护黑点个数，对于一组刚好使$cnt_l+cnt_r\leq k$的$l,r$,且$[l+1,r]$所在子树都与$l$不同时就可以选取$l~and~x\in [l+1,r]$,我们要使$dis_l+dis_x$只需使$dis_x$最大，因此每次递归建$ST$表$RMQ$即可
很奇怪的这道题这样做有$50$分
但$[l+1,r]$所在子树有与$l$相同时至少我就束手无策了
于是我们放弃这个办法
思路第二步:放缩
我们依然不改变点分治本质思想，利用好经过根这个性质
如果不能尺取法贪心,那么$DP$可以吗，两个变量:过的黑点个数，和路径长度，我们想合并的根的不同儿子为根的子树
$\therefore$有$f^{rt}\left[i\right]j$表示以$rt$为根子树中,根到以$i$号儿子为根子树中一点路径上有$j$个黑点的路径最大长度
着眼在经过的黑点数不超过$K$个上，我们有可能会想到放缩，就是我们并不定义死刚好是$j$个黑点，好处等会儿就知道了
$\therefore$有$f^{rt}\left[i\right]j$表示以$rt$为根子树中,根到以$i$号儿子为根子树中一点路径上最多有$j$个黑点的路径最大长度
所求:$Ans=\max\{f^{rt}[x][p],f^{rt}[y][q]\}(p+q+[color_{rt}=”black”]\le k])$
于是这里我们的定义就很好用了，那个$\le$号在实现中就可以取等
为了知道$p,q$的取值范围，我们再定义一个量
$cnt^{rt}i$表示以$rt$为根子树中,根到以$i$号儿子为根子树中一点最多经过的黑点数
$\therefore$ $p\le cnt^{rt}x q\le cnt^{rt}y$
思路第三步:合并
如果我们这样做就要解决这个问题
如何求$\max\{f^{rt}[x][p],f^{rt}[y][q]\}(p+q+[color_{rt}=”black”]\le k])$
有一个办法是暴力，因为对$f^{rt}[x][p],f^{rt}[y][q]$我们都可以$O(n)$求出
复杂度为$O(\frac{n\cdot (n-1)}{2})=O(n^2)$
但我们想并没有必要两两子树比较，由于求$\max$具有传递性,如果我们知道$f^{rt}[s_1][p]>f^{rt}[s_2][p]$我们就完全没有必要保留$f^{rt}[s_2][p]$了
因此我们想到合并
具体来说我们记录两个值，$Now^{rt}_{(i,)x}$/$Past^{rt}_{(i,)x}$分别表示以$rt$为根子树中,根到以$i$号儿子为根子树/以$1\rightarrow i-1$号儿子为根子树经过$x$个黑点的最长路径
但合并的顺序是个问题，每次我们需要比较求$\max$更新$\max\{cnt_1,cnt_2…cnt_i\}$次
由于答案与枚举儿子顺序无关，因此贪心可得对儿子按$cnt_i$从小到大排序即可
小结一下，对于这类最值点分治有一种办法是合并
代码常数大
1 | |
2 | |
3 | |
4 | |
5 | using namespace std; |
6 | template<typename _int> |
7 | inline void read(re _int&x){ |
8 | re _int res=0,flag=1;re char opt; |
9 | while((opt=getchar())>'9'||opt<'0')if(opt=='-')flag=-1; |
10 | while(opt>='0'&&opt<='9'){res=(res<<1)+(res<<3)+opt-'0';opt=getchar();} |
11 | x=res*flag; |
12 | } |
13 | struct Edge{ |
14 | int to,next,v; |
15 | }e[N<<1]; |
16 | int n,k,m,h[N],cnt,size[N],color[N],now[N],past[N],mind,ans=-INF; |
17 | char vis[N]; |
18 | inline void AddEdge(re int x,re int y,re int z){e[++cnt]=(Edge){y,h[x],z};h[x]=cnt;} |
19 | struct Node{ |
20 | int len,son,cnt; |
21 | inline char friend operator<(re Node a,re Node b){return a.cnt<b.cnt;} |
22 | }p[N<<1]; |
23 | inline void dfs_size(re int x,re int prt){ |
24 | re int i,y; |
25 | size[x]=1; |
26 | for(i=h[x];i;i=e[i].next){ |
27 | y=e[i].to;if(y==prt||vis[y])continue; |
28 | dfs_size(y,x); |
29 | size[x]+=size[y]; |
30 | } |
31 | } |
32 | inline void dfs_cnt(re int x,re int prt,re int pos,re int bcnt){ |
33 | re int i,y; |
34 | bcnt+=color[x]; |
35 | if(bcnt>k)return ; |
36 | if(bcnt>p[pos].cnt)p[pos].cnt=bcnt; |
37 | for(i=h[x];i;i=e[i].next){ |
38 | y=e[i].to;if(y==prt||vis[y])continue; |
39 | dfs_cnt(y,x,pos,bcnt); |
40 | } |
41 | } |
42 | inline void dfs_dist(re int x,re int prt,re int dist,re int bcnt){ |
43 | re int i,y; |
44 | bcnt+=color[x]; |
45 | if(bcnt>k)return ; |
46 | if(dist>now[bcnt])now[bcnt]=dist; |
47 | for(i=h[x];i;i=e[i].next){ |
48 | y=e[i].to;if(y==prt||vis[y])continue; |
49 | dfs_dist(y,x,dist+e[i].v,bcnt); |
50 | } |
51 | } |
52 | inline void Center(re int x,re int prt,re int&rt,re int root){ |
53 | re int i,y,maxx=-INF; |
54 | for(i=h[x];i;i=e[i].next){ |
55 | y=e[i].to;if(y==prt||vis[y])continue; |
56 | Center(y,x,rt,root); |
57 | maxx=max(maxx,size[y]); |
58 | } |
59 | maxx=max(maxx,size[root]-size[x]); |
60 | if(maxx<mind){mind=maxx;rt=x;} |
61 | } |
62 | inline void Solve(re int x){ |
63 | re int i,j,y,rt,tot=0,tmp;mind=INF; |
64 | dfs_size(x,0); |
65 | Center(x,0,rt,x); |
66 | vis[rt]=1; |
67 | for(i=h[rt];i;i=e[i].next){ |
68 | y=e[i].to; |
69 | p[++tot]=(Node){e[i].v,y,0}; |
70 | dfs_cnt(y,0,tot,0); |
71 | } |
72 | sort(p+1,p+tot+1); |
73 | for(i=0;i<=p[tot].cnt;++i)past[i]=0; |
74 | for(i=1;i<=tot;++i){ |
75 | y=p[i].son; |
76 | for(j=0;j<=p[i].cnt;++j)now[j]=-INF; |
77 | dfs_dist(y,0,p[i].len,0); |
78 | for(j=1;j<=p[i].cnt;++j)now[j]=max(now[j-1],now[j]); |
79 | for(j=0;j<=p[i].cnt;++j){ |
80 | tmp=min(p[i-1].cnt,k-j-color[rt]);if(tmp<0)continue; |
81 | ans=max(ans,now[j]+past[tmp]); |
82 | } |
83 | for(j=0;j<=p[i].cnt;++j)past[j]=max(past[j],now[j]); |
84 | for(j=1;j<=p[i].cnt;++j)past[j]=max(past[j-1],past[j]); |
85 | } |
86 | for(i=h[rt];i;i=e[i].next){ |
87 | y=e[i].to; |
88 | if(!vis[y])Solve(y); |
89 | } |
90 | } |
91 | inline void Read(void){ |
92 | re int i,x,y,z; |
93 | read(n);read(k);read(m); |
94 | while(m--){read(x);color[x]=1;} |
95 | for(i=1;i<n;++i){read(x);read(y);read(z);AddEdge(x,y,z);AddEdge(y,x,z);} |
96 | } |
97 | int main(void){ |
98 | Read(); |
99 | Solve(1); |
100 | printf("%d\n",ans); |
101 | return 0; |
102 | } |