Description

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

Solution

• 先貼題解：

• 我們將每種顏色的點兩兩看做一組限制，在 N?N 平面上覆蓋矩形。

• 找“ai 下面的 p 點”用倍增可以解決。

• 設有某種顏色的點有 t (t≤20) 個，那么復雜度就是 O(Nt?t2?logN)=O(N?t?logN) 。

• 之后把每個矩形拆成兩組（分別代表加入和刪除），按x坐標排序，用掃描線掃過。

• 維護一顆標記不下傳的線段樹，記錄區間內空點的個數即可。

• 時間復雜度 O(N?t?logN) 。

Code

#include<cstdio> #include<algorithm> #include<vector> #include<cmath> #include<cctype> using namespace std; const int N=1e5+5,M=21; struct data {int x,y1,y2,p; }a[N*M<<2]; struct segment {int sum,c; }f[N<<2]; int n,tot,qx,qy,qz; long long ans; int first[N],nex[N<<1],en[N<<1]; int dfn[N],size[N],dep[N],fa[N][M]; vector<int>c[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48),ch=getchar();return w?-X:X; } inline void insert(int x,int y) {nex[++tot]=first[x];first[x]=tot;en[tot]=y; } void dfs(int x) {dfn[x]=++tot;dep[x]=dep[fa[x][0]]+1;size[x]=1;for(int i=first[x];i;i=nex[i])if(en[i]^fa[x][0]){fa[en[i]][0]=x;dfs(en[i]);size[x]+=size[en[i]];} } inline void cover(int x1,int y1,int x2,int y2) {a[++tot]=(data){x1,y1,y2,1};a[++tot]=(data){x2+1,y1,y2,-1}; } inline bool cmp(data x,data y) {return x.x<y.x; } inline int getlca(int x,int y) {for(int i=log2(dep[y]);i>=0;i--)if(dep[fa[y][i]]>dep[x]) y=fa[y][i];return y; } void make(int v,int l,int r) {f[v].sum=r-l+1;if(l==r) return;int mid=l+r>>1;make(v<<1,l,mid);make(v<<1|1,mid+1,r); } void change(int v,int l,int r) {if(qx<=l && r<=qy){f[v].c+=qz;if(f[v].c) f[v].sum=0; elseif(l==r) f[v].sum=1; elsef[v].sum=f[v<<1].sum+f[v<<1|1].sum;return;}int mid=l+r>>1;if(qx<=mid) change(v<<1,l,mid);if(qy>mid) change(v<<1|1,mid+1,r);if(!f[v].c) f[v].sum=f[v<<1].sum+f[v<<1|1].sum; else f[v].sum=0; } int main() {freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);n=read();for(int i=1;i<=n;i++){int x=read();c[x].push_back(i);}for(int i=1;i<n;i++){int x=read(),y=read();insert(x,y);insert(y,x);}tot=0;dfs(1);for(int j=1;j<17;j++)for(int i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1];tot=0;for(int i=1;i<=n;i++){int num=c[i].size();if(num>1)for(int j=0;j<num-1;j++)for(int k=j+1;k<num;k++){int x=c[i][j],y=c[i][k];if(dfn[x]>dfn[y]) swap(x,y);if(dfn[x]<dfn[y] && dfn[y]<=dfn[x]+size[x]-1){if(fa[y][0]==x){cover(1,dfn[y],dfn[y]-1,dfn[y]+size[y]-1);cover(dfn[y],1,dfn[y]+size[y]-1,dfn[y]-1);if(dfn[y]+size[y]<=n){cover(dfn[y]+size[y],dfn[y],n,dfn[y]+size[y]-1);cover(dfn[y],dfn[y]+size[y],dfn[y]+size[y]-1,n);}}else{int z=getlca(x,y);cover(1,dfn[y],dfn[z]-1,dfn[y]+size[y]-1);cover(dfn[y],1,dfn[y]+size[y]-1,dfn[z]-1);if(dfn[z]+size[z]<=n){cover(dfn[z]+size[z],dfn[y],n,dfn[y]+size[y]-1);cover(dfn[y],dfn[z]+size[z],dfn[y]+size[y]-1,n);}}}else{cover(dfn[x],dfn[y],dfn[x]+size[x]-1,dfn[y]+size[y]-1);cover(dfn[y],dfn[x],dfn[y]+size[y]-1,dfn[x]+size[x]-1);}}}sort(a+1,a+1+tot,cmp);make(1,1,n);for(int i=1,j=1;i<=n;i++){while(j<=tot && a[j].x==i){qx=a[j].y1,qy=a[j].y2,qz=a[j].p;change(1,1,n);j++;}ans+=f[1].sum;}printf("%lld",(ans+n)>>1);return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的JZOJ 5678. 【GDOI2018Day2模拟4.21】果树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。