ZigZagK的博客
[扫描线+线段树]LOJ6276【果树】题解
[扫描线+线段树]LOJ6276【果树】题解
2018年12月20日 19:53
LOJ
查看标签

题目概述

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

解题报告

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

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

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

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

示例程序

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
#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; }
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
本文写于 2293 天前,最后更新于 2293 天前。
部分信息可能已经过时,博主也可能已经无法对其内容进行解答。
OK
  1. 1 Skyscape Plum - Melodic Artist
  2. 2 ほしのおとしもの ああああ
  3. 3 感情の摩天楼 ~ Cosmic Mind 上海アリス幻樂団
  4. 4 秘匿されたフォーシーズンズ 上海アリス幻樂団
  5. 5 Ideal and the Real 小西利樹
  6. 6 Undertale Toby Fox
  7. 7 First Steps Lena Raine
  8. 8 Mirror Temple (Mirror Magic Mix) Lena Raine / 2 Mello
  9. 9 City of Tears Christopher Larkin
  10. 10 Tower Of Heaven (You Are Slaves) Feint
Skyscape - Plum - Melodic Artist
00:00 / 00:00
An audio error has occurred, player will skip forward in 2 seconds.

作曲 : Jeong Min Jae

纯音乐,请欣赏