网站如何留言/百度正版下载恢复百度

解题思路

一道自己出的题目
思路来自谋道类似的随机化题目
首先如果$K=p$怎么做
考虑点分治
算出所有经过重心的路径
记录重心上的颜色种类,这个可以状压一下,记作$sta[i]$
而总的颜色就是$S=(1<<p)-1$
那么两条路径可以拼出答案，当且仅当
$sta[x]|sta[y]==S$
我们枚举$x$，就可以算出最优的$y$
而符合条件的$y$一定是$sta[x]$的补集的超集
预处理处$f[i]={\max }_{j|i==j}va{l}_j$
那么答案就是
$$\underset{i}{\max }va{l}_i+f[S-sta[i]]$$
预处理可以子集枚举，复杂度$3^5$，而这个复杂度是没有和点分治的log一起的
现在$k$很大，不能状压，因此我们可以乱搞一下
考虑把$k$中颜色每一种都随机到$1$到$p$中的一个
那么在最优情况下，答案的p种颜色肯定在不同的类里，因为如果在相同的类里肯定不优
而只要这p种颜色在不同类里，一定能找到他们
因此我们因此随机成功的概率是
错排的数量除以总的排列数，也就是
$$\frac{p!}{p^p}$$
显然这个概率随着$p$的增大而减小
而$p=5$时，是3.84%
也就是说，失败的概率是96.16%
随机130次，这个概率失败的概率已经小于1%
总复杂度是$O(130(nlogn+n{3}^5))$
虽然有10s，但是也很难过去
考虑卡常
首先可以提前建出点分树，不需要每次重构
子集枚举的部分可以用sosdp优化到$5\times 2^5$，就可以过了
复杂度$O(130(nlogn+n\times 5\times 2^5))$

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 6e4+7;
struct edge
{int y,next;
}e[2*N];
int link[N],t=0;
void add(int x,int y)
{e[++t].y=y;e[t].next=link[x];link[x]=t;
}
int col[N];
LL val[N];
int bel[N];
int n,k,p;
LL ans=1e9+7;
int Make(int l,int r)
{int res=0;for(int i=1;i<=7;i++)res=res*10+rand()%10;return res%(r-l+1)+l;
}
void Lisan()
{for(int i=1;i<=k;i++)bel[i]=Make(1,p);
}
edge E[2*N];
int Link[N],T=0;
void Add(int x,int y)
{E[++T].y=y;E[T].next=Link[x];Link[x]=T;
}
int siz[N],son[N];
bool vis[N];
void getroot(int x,int pre,int &root,int tot)
{siz[x]=1;son[x]=0;for(int i=link[x];i;i=e[i].next){int y=e[i].y;if(y==pre||vis[y]) continue;getroot(y,x,root,tot);siz[x]+=siz[y];son[x]=max(son[x],siz[y]);}son[x]=max(son[x],tot-son[x]);if(!root||son[root]>son[x]) root=x;
}
int root;
void Divide(int x)
{vis[x]=1;for(int i=link[x];i;i=e[i].next){int y=e[i].y;if(vis[y])  continue;int r=0;getroot(y,x,r,siz[y]);Add(x,r);Divide(r);}
}
void Build()
{getroot(1,0,root,n);Divide(root);
}
LL dis[N];
int top=0,lastop=0;
int sta[N];
int W;
void getdis(int x,int pre,LL w,int S)
{S|=(1<<(bel[col[x]]-1));w+=val[x];++top;dis[top]=w;sta[top]=S;
//	if(S==W-1) return;for(int i=link[x];i;i=e[i].next){int y=e[i].y;if(y==pre||vis[y]) continue;getdis(y,x,w,S);}
}
LL f[1000];
void rebuild()
{for(int i=0;i<p;i++)for(int j=0;j<W;j++)if(!((j>>i)&1))f[j]=min(f[j],f[j+(1<<i)]);
}
void getans(int x)
{lastop=top=0;for(int i=0;i<W;i++)f[i]=1e9;f[1<<(bel[col[x]]-1)]=val[x];rebuild();for(int i=link[x];i;i=e[i].next){int y=e[i].y;if(vis[y]) continue;getdis(y,x,0,0);for(int j=lastop+1;j<=top;j++)ans=min(ans,dis[j]+f[W-1-sta[j]]); for(int j=lastop+1;j<=top;j++){sta[j]|=(1<<(bel[col[x]]-1));dis[j]+=val[x];}for(int j=lastop+1;j<=top;j++)f[sta[j]]=min(f[sta[j]],dis[j]);rebuild();lastop=top;}
}
void put()
{for(int i=1;i<=n;i++)cout<<bel[col[i]]<<' ';cout<<endl;
}
void solve(int x)
{vis[x]=1;getans(x);for(int i=Link[x];i;i=E[i].next){int y=E[i].y;solve(y);}
}
int main()
{
//	freopen("countdown.in","r",stdin);
//	freopen("countdown.out","w",stdout);srand(time(0));cin>>n>>k>>p;for(int i=1;i<=n;i++)scanf("%lld",&val[i]);for(int i=1;i<=n;i++)scanf("%d",&col[i]);int B = 130;for(int i=1;i<n;i++){int x,y;scanf("%d %d",&x,&y);add(x,y);add(y,x);}Build();W=(1<<p);while(B--){Lisan();for(int i=1;i<=n;i++)vis[i]=0;solve(root);}if(ans==1e9+7)ans=-1;cout<<ans;return 0;
}