c/c++语言开发共享[ncw7] 小睿睿的方案

考虑一对情侣(x,y)x<y的贡献，设in[x],out[x]为数的dfs序。

强制从x走向y方向

• 当in[x]<in[y]且out[y]<=out[x] 矩形{1,in[x],in[y],out[y]},{out[x]+1,n,in[y],out[y]},{(in[x]+1,in[z]-1,in[y],out[y]},{out[z]+1,out[x],in[y],out[y]}，z是x所在的y的儿子子树的根

• 当in[y]<in[x]且out[x]<=out[y] 情况类似

• 其余情况 矩形{in[x],out[x],in[y],out[y]}

这样平面上所有落在矩形内的点p(x,y)x<=y是不合法的。

但是这样并不好算。

于是干脆算出有序点对数，及忽略走向，因为点(x,x)一定不被包含在矩形内，所以答案为(n^2-不合法的有序点对-n)/2。

#include <bits/stdc++.h> using namespace std; const int n=1e5+10;  int head[n],to[n<<1],last[n<<1]; int fa[n][20],dep[n],in[n],out[n];   void add_edge(int x,int y) {     static int cnt=0;     to[++cnt]=y,last[cnt]=head[x],head[x]=cnt; } void dfs(int x,int pa) {     static int cnt=0;     in[x]=++cnt;     dep[x]=dep[fa[x][0]=pa]+1;     for(int i=1; (1<<i)<dep[x]; ++i)          fa[x][i]=fa[fa[x][i-1]][i-1];     for(int i=head[x]; i; i=last[i])          if(to[i]!=pa) dfs(to[i],x);     out[x]=cnt; }  struct tree {     int cover,len; } t[n<<2]; #define ls (x<<1) #define rs (x<<1|1) void update(int x,int l,int r) {     if(t[x].cover) t[x].len=r-l+1;     else if(l==r) t[x].len=0;     else t[x].len=t[ls].len+t[rs].len; } void modify(int x,int l,int r,int l,int r,int w) {     if(l<=l&&r<=r) {         t[x].cover+=w;         update(x,l,r);         return;     }     int mid=(l+r)>>1;     if(l<=mid) modify(ls,l,mid,l,r,w);     if(mid<r) modify(rs,mid+1,r,l,r,w);     update(x,l,r); } #undef ls #undef rs  struct seg {     int type,h,l,r;     bool operator<(const seg&d) const {         return h!=d.h?h<d.h:type<d.type;     } } s[n<<3]; int n,m,cnt; void add_matrix(int a,int b,int c,int d) {     if(a>b||c>d) return;     s[++cnt]=(seg){1,c,a,b};     s[++cnt]=(seg){-1,d+1,a,b}; } long long get_area() {     long long ret=0;     sort(s+1,s+cnt+1);       for(int i=1; i<cnt; ++i) {         modify(1,1,n,s[i].l,s[i].r,s[i].type);         ret+=1ll*(s[i+1].h-s[i].h)*t[1].len;     }     return ret; } void insert(int x,int y) {     if(in[x]<in[y]&&out[y]<=out[x]) {         add_matrix(1,in[x],in[y],out[y]);         add_matrix(out[x]+1,n,in[y],out[y]);         int dif=dep[y]-dep[x]-1,z=y;         for(int i=19; ~i; --i) if((dif>>i)&1) z=fa[z][i];         add_matrix(in[x]+1,in[z]-1,in[y],out[y]);         add_matrix(out[z]+1,out[x],in[y],out[y]);         return;     }      if(in[y]<in[x]&&out[x]<=out[y]) {         add_matrix(in[x],out[x],1,in[y]);         add_matrix(in[x],out[x],out[y]+1,n);         int dif=dep[x]-dep[y]-1,z=x;         for(int i=19; ~i; --i) if((dif>>i)&1) z=fa[z][i];         add_matrix(in[x],out[x],in[y]+1,in[z]-1);         add_matrix(in[x],out[x],out[z]+1,out[y]);         return;     }      add_matrix(in[x],out[x],in[y],out[y]); }   int main() {     scanf("%d%d",&n,&m);     for(int x,y,i=n; --i; ) {         scanf("%d%d",&x,&y);         add_edge(x,y);         add_edge(y,x);     }     dfs(1,0);     for(int x,y,i=1; i<=m; ++i) {         scanf("%d%d",&x,&y);         insert(x,y);         insert(y,x);     }     printf("%lldn",(1ll*n*n-get_area()-n)/2);     return 0; } 

突然想到一道以前的题，直接扔下思路好了（可能有点锅）

rb有一棵树，树的每个节点有个颜色。给一个长度为(n)的颜色序列，定义(s(i,j)) 为(i) 到(j) 的颜色数量。以及
[ sum_i=sum_{j=1}^ns(i,j) ]
现在他想让你求出所有的(sum_i) 。((1le n,c[i]le 10^5))

预处理出树的dfs序（(in[])和(out[])）对于树上的一个点 (v) ，设其颜色是 (c) 。令 ((i,j)) 对应二维平面上的一个点。则 (v) 会对以下两类 (s(i,j)) 产生贡献：

• (i) 和 (j) 一个在(v) 的子树外，一个在子树内。
  1. (iin[1,in_v]) ，(jin[in_v,out_v])
  2. (iin[in_v,out_v]) ，(jin(out_v,n]) 。
  3. (iin[in_v,out_v]) ，(jin[1,in_v]) 。
  4. (iin(out_v,n]) ，(jin[in_v,out_v]) 。
• (i) 和 (j) 分别位于以 (v) 的不同儿子为根的两个子树中。枚举一个儿子(s)
  1. (iin[in_v,in_s))，(jin[in_s,out_s])。
  2. (iin[in_s,out_s])，(jin(out_s,out_v])。
  3. (iin[in_s,out_s])，(jin[in_v,in_s))。
  4. (iin(out_s,out_v])，(jin[in_s,out_s])。

把 ({iindots,jindots}) 看作覆盖在二维平面上的一个矩形。把同是颜色(c) 的点的相关矩形单独讨论，若((i,j)) 被某个矩形覆盖，则表示(irightarrow j) 路径上存在颜色(c) 。

我们考虑进行扫描线，对线所在位置的点进行差分记录位置上被覆盖的点有几个（相应地有一个消除标记），在颜色讨论完后求一个前缀和，那么答案就出来了。