对每个点随机黑白染色，强制答案链的前 \(\lfloor \frac{k}{2}\rfloor\) 个点和后 \(\lceil \frac{k}{2} \rceil\) 个点的颜色不同。
计算答案只需要枚举中间这条两端颜色不同的边 \((u,v,w)\)，然后分成两边计算 \(u,v\) 出发的经过 \(1/2/3\) 个点的最长路径，这一部分可以 \(\Theta(n+m)\) 处理出来。
正确率为 \(\frac{1+[2|k]}{2^{k}}\)，当 \(k=6\) 时为 \(\frac{1}{32}\)。
随机计算 \(B=1000\) 次即可保证正确率，总复杂度 \(\Theta(B\sum (n+m))\)。
实测 \(100\) 次就能过……
当 \(2\le k\le 6\) 时，相比于其余的随机化算法在复杂度和正确率上都有优势。
如果要做 \(k=7,8\)，这样的做法需要 \(\Theta(m\sqrt{m})\)，加上正确率的降低，可能不会更优秀。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define all(a) (a).begin(),(a).end()
#ifdef DEBUG
template<class T>
ostream& operator << (ostream &out,vector<T> a){
out<<'[';
for(T x:a)out<<x<<',';
return out<<']';
}
template<class T>
vector<T> ary(T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<class T>
void debug(T x){
cerr<<x<<endl;
}
template<class T,class...S>
void debug(T x,S...y){
cerr<<x<<' ',debug(y...);
}
#else
#define debug(...) void()
#endif
const int N=1e4+10,INF=1e9;
int T,n,m,k,col[N];
mt19937 rnd(time(0));
int ans,fi[N],se[N],d2[N];
vector<pair<int,int>>to[N];
void solve(){
for(int i=1;i<=n;i++){
fi[i]=se[i]=d2[i]=-INF;
}
auto ins=[&](int u,int w){
if(w>fi[u])se[u]=fi[u],fi[u]=w;
else se[u]=max(se[u],w);
};
for(int u=1;u<=n;u++){
for(auto [v,w]:to[u])if(col[u]==col[v])ins(u,w);
}
auto calc=[&](int u,int w){
return fi[u]==w?se[u]:fi[u];
};
for(int u=1;u<=n;u++){
for(auto [v,w]:to[u])if(col[u]==col[v]){
d2[u]=max(d2[u],w+calc(v,w));
}
}
// debug(ary(col,1,n));
// debug(ary(fi,1,n));
// debug(ary(se,1,n));
// debug(ary(d2,1,n));
for(int u=1;u<=n;u++)if(col[u]){
for(auto [v,w]:to[u])if(!col[v]){
if(k==2)ans=max(ans,w);
else if(k==3)ans=max(ans,w+max(fi[u],fi[v]));
else if(k==4)ans=max(ans,w+fi[u]+fi[v]);
else if(k==5)ans=max({ans,w+d2[u]+fi[v],w+fi[u]+d2[v]});
else ans=max(ans,w+d2[u]+d2[v]);
}
}
}
void get(){
scanf("%d%d%d",&n,&m,&k);
for(int u,v,w;m--;){
scanf("%d%d%d",&u,&v,&w);
to[u].push_back({v,w}),to[v].push_back({u,w});
}
ans=0;
for(int T=1000;T--;){
for(int i=1;i<=n;i++)col[i]=rnd()%2;
solve();
}
if(!ans)puts("impossible");
else printf("%d\n",ans);
}
void clr(){
for(int i=1;i<=n;i++)to[i].clear();
}
int main(){
freopen(".in","r",stdin);
// freopen(".out","w",stdout);
for(scanf("%d",&T);T--;clr())get();
return 0;
}