JOISCD4T1
给定一棵树，每个节点有颜色，每次可以合并两个颜色 使得所有颜色为 的颜色都变成 。求最少的合并次数使得有一个颜色是联通的。
这题我考试的时候看错题自闭一整天
正经做法有两种：点分治和树剖优化建图跑SCC。
点分治
每次钦定这个分治中心的颜色必须选。而之前已经计算过的颜色不能再选了，因为那样不会更优。于是可能被选到的点就被限制在当前分治到的这个联通块中，于是就可以点分治做了。不断迭代地去找需要选的颜色，注意保证复杂度。
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=2e5+50;
int n,k,c[N],f[N],q[N],l,r,st[N],tp,zz[N];bool ban[N],be[N],fail,vvis[N];
vector<int>v[N],vv[N];
int sum,dat,rt,sz[N],ans;bool vis[N];
void findr(int x,int ff){
int mx=0;sz[x]=1;
for(int i=0,y;i<v[x].size();i++)
if(!vis[y=v[x][i]]&&y!=ff)
findr(y,x),sz[x]+=sz[y],mx=max(mx,sz[y]);
mx=max(mx,sum-sz[x]);if(mx<dat)dat=mx,rt=x;
}
void dfs(int x,int ff,int z){
f[x]=ff;if(!ban[c[x]])vv[c[x]].pb(x);
if(!zz[c[x]])zz[c[x]]=z;else if(zz[c[x]]!=z)st[++tp]=c[x];
for(int i=0,y;i<v[x].size();i++)
if(!vis[y=v[x][i]]&&y!=ff)dfs(y,x,f[x]?z:y);
}
void dfs2(int x,int ff){
vv[c[x]].clear(),vvis[x]=0;be[c[x]]=zz[c[x]]=0;
for(int i=0,y;i<v[x].size();i++)
if(!vis[y=v[x][i]]&&y!=ff)dfs2(y,x);
}
void solve(int x){
vis[x]=1;
dfs(x,0,0);be[q[l=r=1]=c[x]]=1;vvis[x]=1;fail=ban[c[x]];
while(l<=r){
int x=q[l++];
for(int i=0;i<vv[x].size();i++){
for(int j=vv[x][i];!vvis[j];j=f[j]){
if(ban[c[j]]){fail=1;break;}vvis[j]=1;
if(!be[c[j]])be[q[++r]=c[j]]=1;
}
if(fail)break;
}
if(fail)break;
}
if(!fail)ans=min(ans,r);
while(tp)ban[st[tp--]]=1;ban[c[x]]=1;
dfs2(x,0);
for(int i=0,y;i<v[x].size();i++)if(!vis[y=v[x][i]])
sum=sz[y],dat=1e9,findr(y,x),solve(rt);
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1,x,y;i<n;i++)
scanf("%d%d",&x,&y),
v[x].pb(y),v[y].pb(x);
for(int i=1;i<=n;i++)scanf("%d",&c[i]);
ans=sum=n;dat=1e9;findr(1,0);solve(rt);
cout<<ans-1;
}
树剖
考虑如果两个颜色 有选了颜色 就必须选颜色 的关系（ 在 的路径上），我们就从 向 连边。这样建好图之后如果要选 就要把所有它能到的点都选上。这其实是一个很经典的模型：显然一个SCC中的点要选会一块选，而一定是选出度为 的SCC比较优。于是建好图跑tarjan就好了。
发现连边其实也是比较显然的。设颜色 的所有点的lca为 ，那么颜色 会向 与所有颜色为 的点的路径上的颜色连边。连树上一条路径的话可以想到树剖优化，但是裸的树剖套线段树是 的，可能过不去。我们只要利用剖出的路径会是一些重链的前缀这个性质，预处理重链前缀的节点就可以做到 。
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=2e5+50,M=6e6+50;
int n,k,f[N],sz[N],d[N],dfn[M],idfn[N],tp[N],clk,rt[N],c[N],ans;
int lc[M],rc[M],rr,cnt,id[N],low[M],st[M],tt,scc,val[M],bel[M];bool ins[M],ban[M];
vector<int>v[N],vv[M],mem[M];
void dfs1(int x){
if(f[x])v[x].erase(find(v[x].begin(),v[x].end(),f[x]));
d[x]=d[f[x]]+1;sz[x]=1;
for(int i=0,y;i<v[x].size();i++){
f[y=v[x][i]]=x,dfs1(y),sz[x]+=sz[y];
if(sz[y]>sz[v[x][0]])swap(v[x][i],v[x][0]);
}
}
void dfs2(int x){
tp[x]^x?vv[id[x]=++cnt].pb(id[f[x]]),vv[cnt].pb(c[x]),0:id[x]=c[x];
idfn[dfn[x]=++clk]=x;
for(int i=0,y;i<v[x].size();i++)
y=v[x][i],tp[y]=i?y:tp[x],dfs2(y);
}
int lca(int x,int y){
for(;tp[x]!=tp[y];x=f[tp[x]])
if(d[tp[x]]<d[tp[y]])swap(x,y);
return d[x]<d[y]?x:y;
}
void build(int &x,int l,int r){
if(l==r){x=c[idfn[l]];return;}
int mid=(l+r)>>1;x=++cnt;
build(lc[x],l,mid);build(rc[x],mid+1,r);
vv[x].pb(lc[x]);vv[x].pb(rc[x]);
}
void query(int x,int l,int r,int ql,int qr,int d){
if(l>qr||r<ql)return;
if(l>=ql&&r<=qr){vv[d].pb(x);return;}
int mid=(l+r)>>1;
query(lc[x],l,mid,ql,qr,d);
query(rc[x],mid+1,r,ql,qr,d);
}
void query(int x,int y,int d){
for(;tp[x]!=tp[y];y=f[tp[y]])vv[d].pb(id[y]);
query(rr,1,n,dfn[x],dfn[y],d);
}
void cmin(int &x,int y){y<x?x=y:0;}
void tarjan(int x){
dfn[x]=low[x]=++clk;
st[++tt]=x;ins[x]=1;
for(int i=0,y;i<vv[x].size();i++)
if(!dfn[y=vv[x][i]])tarjan(y),cmin(low[x],low[y]);
else if(ins[y])cmin(low[x],dfn[y]);
if(low[x]==dfn[x]){
int y;++scc;
do{
y=st[tt--];ins[y]=0;
val[scc]+=y<=k;bel[y]=scc;
mem[scc].pb(y);
}while(y!=x);
}
}
int main(){
scanf("%d%d",&n,&k);cnt=ans=k;
for(int i=1,x,y;i<n;i++)
scanf("%d%d",&x,&y),
v[x].pb(y),v[y].pb(x);
for(int i=1;i<=n;i++)scanf("%d",&c[i]);
dfs1(1);dfs2(tp[1]=1);build(rr,1,n);
for(int i=1;i<=n;i++){int &z=rt[c[i]];z=z?lca(z,i):i;}
for(int i=1;i<=n;i++)query(rt[c[i]],i,c[i]);
memset(dfn,0,sizeof(dfn));clk=0;
for(int i=1;i<=cnt;i++)if(!dfn[i])tarjan(i);
for(int i=1;i<=scc;i++){
for(int j=0;j<mem[i].size();j++){
for(int x=mem[i][j],y,k=0;k<vv[x].size();k++){
if(bel[y=vv[x][k]]!=i&&(val[bel[y]]||ban[bel[y]]))ban[i]=1;
}
}
if(!ban[i]&&val[i])cmin(ans,val[i]);
}
cout<<ans-1;
return 0;
}
正题
在比赛后当天与四川神仙讨论时，他说他就写了个乱搞：倍增lca和tarjan。
当时我就觉得不太会啊，这又是另一种神仙做法吧。
后来讲了题，发现哪种也不是他的，又去问了问他。
他的做法：
对于每个节点，如果它不是所在颜色的lca，那么就把它的颜色向它父亲的颜色连边，然后就跑tarjan找到出度为 的SCC。
很困难地理解了他的意思之后提出了对正确性的质疑，并举了例子。他说：你说的有道理。但这不影响正确性啊。
我看神仙已经有对我烦的意思了，于是也没再多打扰他。
玩了好几个数据发现都没有问题。后来实现了他的做法（优化了一下实现了 ），轻松地拿到了UOJ，LOJ的最短代码和最快代码！发到了群里炫耀，并求助大家正确性的证明。
z7z刚开始很确信这个算法是错误的，并尝试给出hack。他说hack成功了，但其实还是假了。
后来z7z也相信这个算法是正确的了，并给出了感性理解（谁不会感性理解啊）。
我也开始好好思考怎么证明它。我有了一个证明的思路，但是发现有一个地方说不过去。然后就想构造一个这样的数据说不定就有证明的思路呢？？
然后。。这个算法它死了23333333谁也没想到是这样的结局233333。
于是，忍痛亲手hack自己的最优解.jpg
最后放出hack数据结束这篇扯淡23333
7 3
1 2
2 3
3 4
4 5
5 6
6 7
3
1
3
2
1
2
1
错代码还是不要放了，虽然它看起来真的很优秀QAQ