题目描述

雪之国度有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)。

一直想要使用交集优化来优化时间，但是，无法优化。

然后我就懵逼了。

如果我们按顺序加入一些边的话，那么我们就可以保证，加入边之后的答案会最优化。

所以就能得出使用最小生成树这个思路。