题解 P2664 【树上游戏】
__ZJ
2018-03-10 14:44:22
### 扫描线，线段树维护区间覆盖
（画风诡异，真的没有点分治，没有虚树。。。）
**●简要版:**
对每种颜色分别考虑，
每个点会贡献的S(i,j)形成平面上的若干矩形。
然后用扫描线+线段树维护区间覆盖去求得：
只考虑该颜色时的每个sum[u](准确说是sum[u]的差分数组)
把每种颜色得到的sum[u]加起来就是答案了。
**●详细版：**
事先dfs一遍这颗树,对每个点u记录下它的dfs序号。
然后维护出be[u](begin)表示u的子树内最小的dfs序号(显然就是它自己的序号啦)
以及en[u](end)表示u的子树内最大的dfs序号(也就是u子树里最后一个被遍历到的点的序号)
考虑树上的某一个点u，它的颜色为c，假设其它点都是没有颜色的，
那么来考虑一下，这个点会为哪些S(i,j)贡献1的值
显然可以分为两类情况：
1).i为u外面的点，j为x子树内的点。
(或者j为u外面的点，i为u子树内的点)
2).i,j分别为x的不同儿子的子树内的点。
(这样的话，i,j的lca为u嘛)。
现在我们赋予二元组(i,j)几何意义：对应着坐标平面上的一个点(i,j)，
有了二维平面，我们在把之前的两类情况反映到平面上:（建议画图理解）
1).i,j一个为u外面的点，另一个为u子树内的点。
子情况(1)：i=1~be[u],j=be[u]~en[u]
那么这就对应着(1~be[u],be[u]~en[u])这样一个矩形，
子情况(2,类似上面，只是把i,j交换)：i=be[u]~en[u],j=1~be[u]
那么这就对应着(be[u]~en[x],1~be[u])这样一个矩形，
子情况(3): i=be[u]~en[u],j=en[u]~N
那么这就对应着(be[u]~en[u],en[u]~N)这样一个矩形，
子情况(4,类似上面，只是把i,j交换)：i=en[u]~N,j=be[u]~en[u]
那么这就对应着(en[u]~N,be[u]~en[u])这样一个矩形，
2).i,j分别为x的不同儿子的子树内的点。
这里需要枚举u的每个儿子v：
子情况(1)：i=be[u]~(en[v]-1),j=be[v]~en[v]
那么这就对应着(be[u]~(en[v]-1),be[v]~en[v])这样一个矩形，
子情况(2,类似上面，只是把i,j交换)：i=be[v]~en[v],j=be[u]~(en[v]-1)
那么这就对应着(be[v]~en[v],be[u]~(en[v]-1))这样一个矩形，
子情况(3)：i=be[v]~en[v],j=(en[v]+1)~en[u]
那么这就对应着(be[v]~en[v],(en[v]+1)~en[u])这样一个矩形，
子情况(4,类似上面，只是把i,j交换)：i=(en[v]+1)~en[u],j=be[v]~en[v]
那么这就对应着((en[v]+1)~en[u],be[v]~en[v])这样一个矩形，
也就是说，我们把上面这些矩形覆盖在平面上，
如果发现(i,j)这个点被覆盖的话，就表明，i到j的路径上有这么一个颜色。
由于一条路径上的同一个颜色只能计算一次。
所以把相同颜色的点归在一起，然后一种颜色一种颜色去做。
把当前颜色的点产生的矩形全部去覆盖平面，
然后用扫描线+线段树维护区间覆盖去得到每个x位置上y被覆盖的长度y_cover，
y_cover的含义就是，只考虑当前颜色时，sum[x]的值
(当然不用逐个求出每个x位置上y的覆盖长度，这里采用一个数组去记录sum[x]的差分，最后再求一遍前缀就好了)
**●时间复杂度分析：**
显然影响时间复杂度的关键在维护若干矩形的覆盖上面。
对于每个矩形，会存在logN级别的时间花费。
由于每个点最多只会产生常数k个矩形
所以，复杂度就O(K*N*logN).
但是每个点会产生的矩形最多有8个，
所以复杂度里的K再乘上线段树的覆盖和查询次数也就相当于一个logN了，
这也是这个做法跑得比较慢的原因。
** 至于点分治的做法，推荐这个很棒的题解：
https://www.luogu.org/blog/user24559/solution-p2664**
~~（那个read()是真的被卡常了，并不是个人觉得写起来比scanf()顺手，迷...）~~
```cpp
#include<bits/stdc++.h>
#define MAXN 100050
#define INF 0x3f3f3f3f
using namespace std;
int N,dnt,snt;
int be[MAXN],en[MAXN],fa[MAXN];
long long cc[MAXN],ANS[MAXN];
struct List{
int lnt;
int to[MAXN*2],nxt[MAXN*2],head[MAXN];
List():lnt(2){}
void Add(int c,int u){
to[lnt]=u; nxt[lnt]=head[c]; head[c]=lnt++;
}
}CL,E;
struct Segment{
//Every vertice can lead to (4 + the num of son*4) Plates. In the other words there are 2*4*2*N segments at most.
int x,yl,yr,k;
bool operator < (const Segment &rtm) const{
return x<rtm.x||(x==rtm.x&&k>rtm.k);
}
}S[MAXN*16];
struct SGT{
//The Segment Tree are used to maintain the cover of the line.
int size,root;
int ls[MAXN*2],rs[MAXN*2],cover[MAXN*2],tag[MAXN*2];
void Pushup(int u,int l,int r){
cover[u]=tag[u]?(r-l+1):cover[ls[u]]+cover[rs[u]];
}
void Modify(int &u,int l,int r,int al,int ar,int k){
if(!u) u=++size;
if(al<=l&&r<=ar) return (void)(tag[u]+=k,Pushup(u,l,r));
int mid=(l+r)>>1;
if(al<=mid) Modify(ls[u],l,mid,al,ar,k);
if(mid<ar) Modify(rs[u],mid+1,r,al,ar,k);
Pushup(u,l,r);
}
}DT;
void dfs(int u,int dad){
be[u]=++dnt; fa[u]=dad;
for(int e=E.head[u];e;e=E.nxt[e]){
int v=E.to[e]; if(v==dad) continue;
dfs(v,u);
}
en[u]=dnt;
}
void insplate(int x1,int x2,int y1,int y2){
if(x1>x2||y1>y2) return;
S[++snt]=(Segment){x1,y1,y2,1};
S[++snt]=(Segment){x2+1,y1,y2,-1};
}
void read(int &x){
static int sign; static char ch;
x=0; sign=1; ch=getchar();
for(;ch<'0'||'9'<ch;ch=getchar()) if(ch==-'-') sign=-1;
for(;'0'<=ch&&ch<='9';ch=getchar()) x=x*10+ch-'0';
x=x*sign;
}
int main(){
read(N); int minc=INF,maxc=0;
for(int i=1,c;i<=N;i++)
read(c),CL.Add(c,i),
minc=min(minc,c),maxc=max(maxc,c);
for(int i=1,a,b;i<N;i++)
read(a),read(b),E.Add(a,b),E.Add(b,a);
dfs(1,0);
for(int c=minc,u,ycover;c<=maxc;c++){
snt=0; ycover=0;
for(int i=CL.head[c];i;i=CL.nxt[i]){
u=CL.to[i];
insplate(1,be[u],be[u],en[u]);
insplate(be[u],en[u],1,be[u]);
insplate(be[u],en[u],en[u]+1,N);
insplate(en[u]+1,N,be[u],en[u]);
for(int e=E.head[u];e;e=E.nxt[e]){
int v=E.to[e]; if(v==fa[u]) continue;
insplate(be[u],be[v]-1,be[v],en[v]);
insplate(be[v],en[v],be[u],be[v]-1);
insplate(be[v],en[v],en[v]+1,en[u]);
insplate(en[v]+1,en[u],be[v],en[v]);
}
}
sort(S+1,S+snt+1);
for(int i=1;i<=snt;i++){
cc[S[i-1].x]+=ycover;
cc[S[i].x]-=ycover;
DT.Modify(DT.root,1,N,S[i].yl,S[i].yr,S[i].k);
ycover=DT.cover[DT.root];
}
}
for(int i=1;i<=N;i++) ANS[i]=ANS[i-1]+cc[i];
for(int i=1;i<=N;i++) printf("%lld\n",ANS[be[i]]);
return 0;
}
```