JZOJ5678. 【GDOI2018Day2模拟4.21】果树

题目描述

NiroBC 姐姐是个活泼的少女，她十分喜欢爬树，而她家门口正好有一棵果树，正好满足了她爬树的需求。
这颗果树有N个节点，节点标号 1…N。每个节点长着一个果子，第i个节点上的果子颜色为 Ci 。
NiroBC姐姐每天都要爬树，每天都要选择一条有趣的路径 (u,v) 来爬。
一条路径被称作有趣的，当且仅当这条路径上的果子的颜色互不相同。
(u,v) 和 (v,u) 被视作同一条路径。特殊地，(i,i) 也被视作一条路径，这条路径只含 i 一个果子，显然是有趣的。
NiroBC姐姐想知道这颗树上有多少条有趣的路径。

Input
第一行，一个整数 N，表示果树的节点个数。
第二行，N 个整数 C1 ,C2 ,…,CN ，表示 N 个果子的颜色。
接下来 N−1 行，每行两个整数 ui ,vi ，表示 ui和vi 之间有一条边
数据保证这N−1条边构成一棵树。
Output
一个整数，表示有趣的路径的数量。

Sample Input
输入1：
3
1 2 3
1 2
1 3

输入2：
5
1 1 2 3 3
1 2
1 3
2 4
2 5
Sample Output
输出1：
6
样例解释：有 (1,1),(1,2),(1,3),(2,2),(2,3),(3,3) 共 6 条有趣的路径。

输出2：
8
样例解释：有 (1,1),(1,3),(2,2),(2,4),(2,5),(3,3),(4,4),(5,5) 共 8 条有趣的路径。

Data Constraint
$1≤N≤10^5,1≤Ci≤N,$ 同种颜色在树上出现不超过20次
部分分不写

12%

暴力？
既然会25%为什么要想12%

37%

暴力
从每个点开始走

67%

部分分真多

既然是一条链，所以起点和终点一定是单调递增的
线性扫过去

（不知道这样做能不能扩展到树上）

100%

题目说同种颜色的点最多只有20个，所以可以搞事
如果可以求出那些路径不合法，那么就可以算出合法方案。

设当前点对为(a,b)，那么有两种情况：
①a和b之间有亲缘关系

假设a是b的祖先，不合法路径一定是在红圈和篮圈里任意的点对

设p是a~b路径中与a距离为1的点（可以暴力求）
那么红圈的点在b的子树内，篮圈的点不在p的子树内

自己理解

②a和b之间没有亲缘关系

那么一定是这样

一个在a的子树内，一个在b的子树内

所以可以用dfs序来搞一搞

设一个点(u,v)表示u到v之间的路径(u和v都是dfs序)
那么每次删掉的路径一定是一个（或两个）矩形

这样问题可以转化为
在一个平面(n*n)上有若干个矩形，求没有被矩形覆盖的格子的个数

可以用扫描线+线段树来搞

不下传标记

话说我好像是第一次写欸
之前一次写炸了

因为矩形的性质，每次加和删的区间都是向对应的
所以不必下传标记

至于统计被覆盖的点个数，如果直接处理会出错
（比如有多个区间互相覆盖就会算重）

所以如果当前区间被覆盖，则覆盖的点个数为区间长度，否则为子区间的和

实现

void change(int t,int l,int r,int x,int y,int s)
{int mid=(l+r)/2;if (x<=l && r<=y){tr[t][0]+=s;tr[t][1]=(!tr[t][0])?(l==r?0:tr[t<<1][1]+tr[(t<<1)+1][1]):(r-l+1);//同下return;}if (x<=mid) change(t<<1,l,mid,x,y,s);if (mid<y)  change((t<<1)+1,mid+1,r,x,y,s);if (!tr[t][0])//这里没有直接上传，而是当区间未被覆盖是才从子区间上传tr[t][1]=tr[t<<1][1]+tr[(t<<1)+1][1];
}

code

#include <iostream>
#include <cstdlib>
#include <cstdio>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
using namespace std;int tr[400001][2];
int a[200001][2];
int A[8000001][4];
int ls[100001];
int c[100001][21];
int C[100001];
int bg[100001];
int ed[100001];
int n,i,j,k,l,len,Len,x,y;
long long ans;void add(int x,int y,int z,int s) {Len++;A[Len][0]=x;A[Len][1]=y;A[Len][2]=z;A[Len][3]=s;}
bool pa(int x,int y) {return bg[x]<=bg[y] && ed[y]<=ed[x];}
void swap(int &x,int &y) {int z=x;x=y;y=z;}void New(int x,int y)
{len++;a[len][0]=y;a[len][1]=ls[x];ls[x]=len;
}void init(int t,int fa)
{bg[t]=++j;for (int i=ls[t]; i; i=a[i][1])if (a[i][0]!=fa) init(a[i][0],t);ed[t]=j;
}void qsort(int l,int r)
{int i,j,mid;i=l;j=r;mid=A[(l+r)/2][2];while (i<=j){while (A[i][2]<mid) i++;while (A[j][2]>mid) j--;if (i<=j){swap(A[i][0],A[j][0]);swap(A[i][1],A[j][1]);swap(A[i][2],A[j][2]);swap(A[i][3],A[j][3]);i++,j--;}}if (l<j) qsort(l,j);if (i<r) qsort(i,r);return;
}void change(int t,int l,int r,int x,int y,int s)
{int mid=(l+r)/2;if (x<=l && r<=y){tr[t][0]+=s;tr[t][1]=(!tr[t][0])?(l==r?0:tr[t<<1][1]+tr[(t<<1)+1][1]):(r-l+1);return;}if (x<=mid) change(t<<1,l,mid,x,y,s);if (mid<y)  change((t<<1)+1,mid+1,r,x,y,s);if (!tr[t][0])tr[t][1]=tr[t<<1][1]+tr[(t<<1)+1][1];
} int main()
{freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);scanf("%d",&n);fo(i,1,n){scanf("%d",&j);c[j][++C[j]]=i;}fo(i,2,n){scanf("%d%d",&j,&k);New(j,k),New(k,j);}j=0;init(1,0);fo(i,1,n){fo(j,1,C[i]-1){fo(k,j+1,C[i]){x=c[i][j],y=c[i][k];if (pa(x,y) || (pa(y,x))){if (pa(y,x)) swap(x,y);for (l=ls[x]; l && !(pa(x,a[l][0]) && pa(a[l][0],y)); l=a[l][1]);l=a[l][0];if (bg[l]>1){add(1,bg[l]-1,bg[y],1);if (ed[y]<n) add(1,bg[l]-1,ed[y]+1,-1);}if (ed[l]<n){add(ed[l]+1,n,bg[y],1);if (ed[y]<n) add(ed[l]+1,n,ed[y]+1,-1);}add(bg[y],ed[y],1,1),add(bg[y],ed[y],bg[l],-1);if (ed[l]<n) add(bg[y],ed[y],ed[l]+1,1);}else{add(bg[x],ed[x],bg[y],1);if (ed[y]<n) add(bg[x],ed[x],ed[y]+1,-1);add(bg[y],ed[y],bg[x],1);if (ed[x]<n) add(bg[y],ed[y],ed[x]+1,-1);}}}}qsort(1,Len);A[Len+1][2]=n+1;ans=(A[1][2]-1)*n;fo(i,1,Len){change(1,1,n,A[i][0],A[i][1],A[i][3]);if (i==len || A[i][2]<A[i+1][2])ans+=(A[i+1][2]-A[i][2])*(n-tr[1][1]);}printf("%lld\n",(ans+n)/2);fclose(stdin);fclose(stdout);return 0;
}