(咕咕咕咕咕)
(先挖坑)
填坑
题意：有一颗树，树上每个点有一个颜色，定义合法的路径为一条路径上所有点颜色都不相同，求有多少合法路径
观察题面，题中有一个条件为每种颜色的点不超过20个，于是想到一种特殊的做法，枚举每种颜色中的点对，对于一个点对u,v，如果u是v的祖宗，则一个在v的子树里的点和一个不在与v所在相同的u的子树里的点是不合法的路径，如果u,v不是祖孙关系，则一个在u的子树与一个在v的子树里的点的路径是不合法的。我们将这些不合法的点对的起点与终点看作二维平面的x和y，将不合法的点对看作一个个矩形，因为这些点对都是在子树中的，所以先处理下dfs序就可以了，然后跑一个扫描线，剪掉不合法的就ok了（我扫描线不会写真是菜死了），在扫描线的时候应该要注意，起点和终点反过来计算重复的问题，我采用的方法是只考虑dfs序中起点大于终点的情况。
代码如下
#include<cstdio> #include<algorithm> #include<vector> using namespace std; typedef long long ll; const int N=1e5+5; struct tree { int l,r,sum,lz,LZ; }t[N*4]; struct edge { int to,next; }e[N*2]; struct name { int l,r,q; name(){} name(int a,int b,int c) { l=a,r=b,q=c; } friend inline bool operator <(const name &a,const name &b) { return a.q>b.q; } }; int head[N],ecnt; int n,c[N]; ll ans; vector<int>vt[N]; vector<name>v[N]; void add(int u,int v) { e[++ecnt].to=v;e[ecnt].next=head[u];head[u]=ecnt; } int ti,dfn[N],pos[N],ed[N]; void dfs(int u) { dfn[u]=++ti;pos[ti]=u; for(int i=head[u];i;i=e[i].next) if(!dfn[e[i].to]) dfs(e[i].to); ed[u]=ti; } void build(int p,int l,int r) { t[p].l=l;t[p].r=r;t[p].sum=0;t[p].lz=t[p].LZ=0; if(l==r) return (void)(t[p].sum=1); int mid=l+r>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); t[p].sum=t[p<<1].sum+t[p<<1|1].sum; } //只考虑dfs序起点大于终点的情况 void adds(int xs,int xe,int ys,int ye) { if(xs>xe||ys>ye) return ; if(xs>ys) swap(xs,ys),swap(xe,ye); v[xs].push_back(name(ys,ye,-1)); v[xe+1].push_back(name(ys,ye,1)); //printf("%d-%d//%d-%d ",xs,xe,ys,ye); } void work(int u,int v) { if(dfn[u]>dfn[v]) swap(u,v); if(dfn[v]>dfn[u] && dfn[v]<=ed[u]) { for(int i=head[u],x;i;i=e[i].next) { x=e[i].to; if(dfn[v]>=dfn[x] && dfn[v]<=ed[x]) { adds(1,dfn[x]-1,dfn[v],ed[v]); adds(ed[x]+1,n,dfn[v],ed[v]); } } } else { adds(dfn[u],ed[u],dfn[v],ed[v]); } } void push_down(int p) { if(t[p].l==t[p].r) return ; if(t[p].lz==0) return ; t[p<<1].lz+=t[p].lz; t[p<<1].LZ+=t[p].lz; if(t[p<<1].LZ<0) t[p<<1].sum=0; else t[p<<1].sum=t[p<<1].r-t[p<<1].l+1; t[p<<1|1].lz+=t[p].lz; t[p<<1|1].LZ+=t[p].lz; if(t[p<<1|1].LZ<0) t[p<<1|1].sum=0; else t[p<<1|1].sum=t[p<<1|1].r-t[p<<1|1].l+1; t[p].lz=0; } void modify(int p,int l,int r,int w) { if(t[p].l==l &&t[p].r==r) { t[p].lz+=w; if(t[p].lz<0) t[p].sum=0; else if(l==r) t[p].sum=1; else t[p].sum=t[p<<1].sum+t[p<<1|1].sum; return ; } // push_down(p); int mid=t[p].l+t[p].r>>1; if(mid>=r) modify(p<<1,l,r,w); else if(l>mid) modify(p<<1|1,l,r,w); else modify(p<<1,l,mid,w),modify(p<<1|1,mid+1,r,w); if(t[p].lz==0)t[p].sum=t[p<<1].sum+t[p<<1|1].sum; } int query(int p,int l,int r) { if(t[p].l==l &&t[p].r==r) return /*printf("(%d,%d,%d)",l,r,t[p].sum),*/t[p].sum; int mid=t[p].l+t[p].r>>1; if(mid>=r) return query(p<<1,l,r); if(l>mid) return query(p<<1|1,l,r); return query(p<<1,l,mid)+query(p<<1|1,mid+1,r); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&c[i]),vt[c[i]].push_back(i); for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),add(u,v),add(v,u); dfs(1); // for(int i=1;i<=n;i++) printf("%d(%d) ",i,dfn[i]); for(int i=1,sz;i<=n;i++) { sz=vt[i].size(); for(int j=0;j<sz;j++) for(int k=j+1;k<sz;k++) work(vt[i][j],vt[i][k]); } build(1,1,n); for(int i=1,sz;i<=n;i++) { sz=v[i].size(); sort(v[i].begin(),v[i].end()); for(int j=0;j<sz;j++) { name u=v[i][j]; modify(1,u.l,u.r,u.q); // printf("%d:%d-%d(%d) ",i,u.l,u.r,u.q); } int FAQ=query(1,i,n); // printf("QUERY%d=%d ",i,FAQ); ans+=FAQ; } printf("%lld ",ans); return 0; } // 3 1 2 3 1 2 1 3 // 5 1 1 2 3 3 1 2 1 3 2 4 2 5