题目描述
雪之国度有N座城市，依次编号为1到N，又有M条道路连接了其中的城市，每一条道路都连接了不同的2个城市，任何两座不同的城市之间可能不止一条道路。雪之女王赋予了每一座城市不同的能量，其中第i座城市被赋予的能量为Wi。
如果城市u和v之间有一条道路，那么只要此刻雪之女王的能量不小于|Wu-Wv|，这条道路就是安全的。如果城市u和v之间存在两条没有重复道路的安全路径（其中每一段道路都是安全的），则认为这两座城市之间有着良好的贸易关系。
最近，雪之女王因为情感问题，她的能量产生巨大的波动。为了维持雪之国度的经济贸易，她希望你能帮忙对Q对城市进行调查。对于第j对城市uj和vj，她希望知道在保证这两座城市之间有着良好贸易关系的前提之下，自己最少需要保持多少的能量。
数据范围
对于20％的数据来说，3<=N<=10, 3<=M<=20, 1<=Q<=10
对于另30％的数据来说，Wi=0
对于100％的数据来说，3<=N<=100000, 3<=M<=500000, 1<=Q<=100000, 每一座城市的能量Wi满足0<=Wi<=200000.
=w=
对原树进行最小生成树，一开始所有树边，对剩余的边按权值从小到大进行操作：
对于一条(u,v,w)的边，在最小生成树上(u,v)的这条路径上的所有标记为未修改的边权改为w，并把它们标记为已修改。
所有边都加入了以后，对于每个询问(u,v)，都使用LCA求树上路径的最大值即可。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define sqr(x) ((x)*(x))
#define ln(x,y) int(log(x)/log(y))
using namespace std;
const char* fin="tour.in";
const char* fout="tour.out";
const int inf=0x7fffffff;
const int maxn=100009,maxm=maxn*2,maxk=17;
int n,m,q,i,j,k;
int a[maxn],b[maxn];
int fi[maxn],la[maxm],ne[maxm],tot;
int fa[maxn][maxk],de[maxn];
void add_line(int a,int b){
tot++;
ne[tot]=fi[a];
la[tot]=b;
fi[a]=tot;
}
void pre(int v,int from){
int i,j,k;
de[v]=de[from]+1;
for (i=1;i<maxk;i++) fa[v][i]=fa[fa[v][i-1]][i-1];
for (k=fi[v];k;k=ne[k])
if (la[k]!=from){
fa[la[k]][0]=v;
pre(la[k],v);
}
}
void up(int &a,const int &i,int &ans){
ans+=1<<i;
a=fa[a][i];
}
int lca(int a,int b){
int i,j,k=0;
if (de[a]<de[b]) swap(a,b);
for (i=maxk-1;i>=0;i--) if (de[fa[a][i]]>de[b]) up(a,i,k);
if (de[a]!=de[b]) up(a,0,k);
for (i=maxk-1;i>=0;i--) if (fa[a][i]!=fa[b][i]) up(a,i,k),up(b,i,k);
if (a!=b) up(a,0,k),up(b,0,k);
return k;
}
struct path{
int x,y,len;
void init(){
x=y=len=0;
}
path(){
init();
}
void get(const int &X,const int &Y,const int &Len){
if (Len>len){
x=X;
y=Y;
len=Len;
}
}
void update(int A,int B);
}li[maxn],Old,Ans,New;
void path::update(int A,int B){
if (A==0 || B==0) return;
int i=lca(A,B);
if (a[A]!=a[B]) Ans.get(A,B,i);
if (i>len) get(A,B,i);
}
path merge(const path &a,const path &b){
path c;
if (a.x==0) return b;
if (b.x==0) return a;
if (a.len>b.len) c.get(a.x,a.y,a.len);
else c.get(b.x,b.y,b.len);
c.update(a.x,b.x);
c.update(a.x,b.y);
c.update(a.y,b.x);
c.update(a.y,b.y);
return c;
}
void dfs(int v,int from){
int i,j,k,co=a[v];
New.init();
New.x=New.y=v;
li[co]=merge(li[co],New);
for (k=fi[v];k;k=ne[k])
if (la[k]!=from) dfs(la[k],v);
}
int main(){
freopen(fin,"r",stdin);
freopen(fout,"w",stdout);
scanf("%d%d%d",&n,&m,&q);
for (i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for (i=1;i<n;i++){
scanf("%d%d",&j,&k);
add_line(j,k);
add_line(k,j);
}
pre(1,0);
dfs(1,0);
for (i=1;i<=q;i++){
scanf("%d",&j);
Old.init();
Ans.init();
b[0]=0;
for (;j;j--){
scanf("%d",&b[++b[0]]);
Old=merge(Old,li[b[b[0]]]);
}
Ans.len++;
if (Ans.len==1) printf("-1\n");
else printf("%d\n",Ans.len);
}
return 0;
}=o=
我认为这一道题最难点在于想出：最小生成树。
我在比赛时做这一道题，想着对于每一个询问，二分答案后使用边双来判断答案是否合法。
但是这个时间复杂度会是O(q∗log∗n)。
一直想要使用交集优化来优化时间，但是，无法优化。
然后我就懵逼了。
如果我们按顺序加入一些边的话，那么我们就可以保证，加入边之后的答案会最优化。
所以就能得出使用最小生成树这个思路。