题目概述

一棵 $n$ 个节点的树，每个节点有颜色，求路径上没有相同颜色的路径个数，每种颜色出现次数不超过 $20$ 。

解题报告

填联赛前的坑，模拟考的时候我疯狂想容斥，我都想到用正解做链了却没想到正解显然可以用到树上……

我们先来考虑链的情况，会发现对于一个点，不能到和这个点颜色相同的点之间的点，也就是说不能到的点是这些线段的并……

于是考虑树上，会发现两个颜色相同的点的子树之间是不能到达的（如果两个点是祖先后代关系就是一棵子树不能到达除自己子树外的其他节点），那么这些限制实际上是在DFS序上连续的，也就是说这是矩形覆盖。

所以扫描线就行啦……每次统计每个点不能到达的节点个数，就可以得到答案。

示例程序

感觉线段树标记不下传要好写很多。

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=100000,Log=17;

int n,dep[maxn+5],Lt[maxn+5],Rt[maxn+5],ST[maxn+5][Log+5];vector<int> p[maxn+5];
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5];
vector< pair<int,int> > s[maxn+5];vector< pair<int,int> > t[maxn+5];
int cov[(maxn<<2)+5],sum[(maxn<<2)+5];LL ans;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return (l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r))?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void Dfs(int x,int pre=0){
    dep[x]=dep[pre]+1;Lt[x]=++Lt[0];ST[x][0]=pre;for (int j=1;j<=Log;j++) ST[x][j]=ST[ST[x][j-1]][j-1];
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Dfs(son[j],x);Rt[x]=Lt[0];
}
#define Miner(x,y) (dep[x]<dep[y]?(x):(y))
inline int LCA(int x,int y){
    if (dep[x]<dep[y]) swap(x,y);for (int j=Log;dep[x]>dep[y]&&~j;j--) if (dep[ST[x][j]]>=dep[y]) x=ST[x][j];
    if (x==y) return x;for (int j=Log;~j;j--) if (ST[x][j]!=ST[y][j]) x=ST[x][j],y=ST[y][j];return ST[x][0];
}
inline int getfa(int x,int k) {for (int j=Log;~j;j--) if (k>>j&1) x=ST[x][j];return x;}
inline void Limit(int l,int r,int L,int R){
    if (l>r||L>R) return;
    s[l].push_back(mp(L,R));t[r+1].push_back(mp(L,R));
    s[L].push_back(mp(l,r));t[R+1].push_back(mp(l,r));
}
inline void Pushup(int p,int l,int r) {sum[p]=0;if (l<r) sum[p]=sum[p<<1]+sum[p<<1|1];if (cov[p]) sum[p]=r-l+1;}
void Cover(int L,int R,int k,int l=1,int r=n,int p=1){
    if (L==l&&r==R) return cov[p]+=k,Pushup(p,l,r);int mid=l+(r-l>>1);
    if (R<=mid) Cover(L,R,k,l,mid,p<<1); else if (L>mid) Cover(L,R,k,mid+1,r,p<<1|1);
    else Cover(L,mid,k,l,mid,p<<1),Cover(mid+1,R,k,mid+1,r,p<<1|1);Pushup(p,l,r);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);ans=(LL)n*(n-1);for (int i=1,x;i<=n;i++) readi(x),p[x].push_back(i);
    for (int i=1,x,y;i<n;i++) readi(x),readi(y),Add(x,y),Add(y,x);Dfs(1);
    for (int c=1;c<=n;c++)
        for (int i=1,si=p[c].size();i<si;i++)
            for (int j=0;j<i;j++){
                int x=p[c][i],y=p[c][j],lca=LCA(x,y);if (y==lca) swap(x,y);
                if (x!=lca&&y!=lca) Limit(Lt[x],Rt[x],Lt[y],Rt[y]);
                else x=getfa(y,dep[y]-dep[x]-1),Limit(1,Lt[x]-1,Lt[y],Rt[y]),Limit(Rt[x]+1,n,Lt[y],Rt[y]);
            }
    for (int i=1;i<=n;ans-=sum[1],i++){
        for (int j=0,si=s[i].size();j<si;j++) Cover(s[i][j].fr,s[i][j].sc,1);
        for (int j=0,si=t[i].size();j<si;j++) Cover(t[i][j].fr,t[i][j].sc,-1);
    }printf("%lld\n",(ans>>1)+n);return 0;
}