给出一棵树,每个点有一种颜色.求断开树上的第i条边后,得到的两个连通块有多少种共有的颜色.

链接

题解

2016湖南省赛的题目

首先可以以1位根建树.然后断开一条边求颜色相交数可以视为求某个子树所拥有的颜色数减去其独有的颜色数.问题转化为了DFS序上的区间询问问题.

很显然,因为没有修改操作,可以使用莫队来做,但时间复杂度较高.下面使用树状数组解决这一问题.

一遍DFS完成建树并得到DFS序之后,可以得到一个颜色序列.第i位的颜色就是DFS序中第i位的节点的颜色.根据上面的推导,分两部分计算答案.

首先对所有的询问操作按照右端点排序,然后从1到n扫描.当扫描到第i位的时候,设这一位的颜色是x,x上次出现的位置为pre.则对于左端点在[pre+1,i]的询问,第一部分的贡献加1;假设x最后一次出现的位置就是i,设其最早出现的位置是p,那么对于左端点在[1,p]的询问,第二部分的贡献增加-1.利用树状数组打差分标记处理上面的操作即可.然后在处理完毕后,进行单点询问就可以得到答案.时间复杂度:

O(Tnlogn)

P.S. 貌似还有启发式合并做法.

PP.S. 11.16日补充了启发式合并做法

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 100010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define bit(x) (x&(-x))
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,i,x,y,lsum=1,tot;
int a[N],l[N],r[N],pre[N],head[N],w[N],Ans[N],d[N],t[N];

struct Edge{
    int t,next,l;
}e[N*4];

struct Data{
    int x,y;
};

vector <Data> q[N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline void Clear(){
    memset(e,0,sizeof(e));  memset(head,0,sizeof(head));
    memset(l,0,sizeof(l));  memset(r,0,sizeof(r));
    memset(pre,0,sizeof(pre));  memset(w,0,sizeof(w));
    memset(d,0,sizeof(d));  memset(t,0,sizeof(t));
    for (register int i=1;i<=n;i++)    q[i].clear();
}

inline void Add(int s,int t,int l){
    e[lsum].t=t;    e[lsum].l=l;    e[lsum].next=head[s];   head[s]=lsum++;
}

inline void Dfs(int x){
    int i=0;
    w[x]=++tot; d[tot]=x;
    for (i=head[x];i;i=e[i].next){
        if (w[e[i].t])   continue;
        Dfs(e[i].t);
        q[tot].push_back((Data){w[e[i].t],e[i].l});
    }
}

inline void Ready(){
    int i=0;
    Dfs(1);
/*    for (i=1;i<=n;i++)
        for (auto j : q[i])
            cout<<i<<" "<<j.x<<" "<<j.y<<endl;*/
    for (i=1;i<=n;i++)  r[a[d[i]]]=i;
    for (i=n;i;i--) l[a[d[i]]]=i;
}

inline void Add(int x,int val){
    for (register int i=x;i<=n;i+=bit(i))   t[i]+=val;
}

inline int Query(int x){
    int sum=0;
    for (register int i=x;i;i-=bit(i))  sum+=t[i];
    return sum;
}

inline void Work(){
    int i=0;
    for (i=1;i<=n;i++){
        Add(pre[a[d[i]]]+1,1);    Add(i+1,-1);
        pre[a[d[i]]]=i;
        if (i==r[a[d[i]]])  Add(1,-1),Add(l[a[d[i]]]+1,1);
        for (auto j : q[i]) Ans[j.y]=Query(j.x);
    }
    for (i=1;i<n;i++)  printf("%d\n",Ans[i]);
}

int main(){
    while (~scanf("%d",&n)){
        Clear();    lsum=1; tot=0;
        for (i=1;i<=n;i++)  a[i]=read();
        for (i=1;i<n;i++){
            x=read();   y=read();
            Add(x,y,i);   Add(y,x,i);
        }
        Ready();    Work();
    }
    return 0;
}

启发式合并:

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define N 100010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,i,x,y,lsum=1;
int head[N],a[N],fa[N],Ans[N],s[N];

struct Edge{
    int t,next,l;
}e[N*2];
map <int,int> M[N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline void Add(int s,int t,int l){
    e[lsum].t=t;    e[lsum].l=l;    e[lsum].next=head[s];   head[s]=lsum++;
}

inline void Clear(){
    memset(head,0,sizeof(head));    memset(Ans,0,sizeof(Ans));
    memset(s,0,sizeof(s));  memset(e,0,sizeof(e));
    memset(fa,0,sizeof(fa));
    for (register int i=1;i<=n;i++) M[i].clear();
}

inline int Dfs(int x,int FA){
    int sum=0;
    for (register int i=head[x];i;i=e[i].next){
        if (e[i].t==FA) continue;
        Ans[e[i].l]=Dfs(e[i].t,x);
        if (M[fa[e[i].t]].size()>M[fa[x]].size())   Swap(fa[e[i].t],fa[x]);
        for (auto j : M[fa[e[i].t]])    M[fa[x]][j.first]+=j.second;
    }
    M[fa[x]][a[x]]++;
    for (auto j : M[fa[x]])
        if (j.second==s[j.first])   sum++;
    return M[fa[x]].size()-sum;
}

inline void Write(int x) {
    static int sta[15];
    register int top=0;
    do{
        sta[top++]=x%10,x/=10;
    }while (x);
    while (top) putchar(sta[--top]+48);
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    while (~scanf("%d",&n)){
        lsum=1; Clear();
        for (i=1;i<=n;i++)  a[i]=read(),fa[i]=i,s[a[i]]++;
        for (i=1;i<n;i++){
            x=read();   y=read();
            Add(x,y,i); Add(y,x,i);
        }
        Dfs(1,0);
        for (i=1;i<n;i++)   Write(Ans[i]),putchar(10);
    }
    return 0;
}