正題

題目鏈接:https://www.luogu.org/problemnew/show/P3085

---

題目大意

一棵樹只有$?1$和$1$的邊權，詢問有多少條路徑可以找到一個分界點使得分出的兩條路徑長度為$0$。

---

解題思路

詢問路徑顯然點分治一波。

然后考慮分界點的兩種情況

分界點在當前掃描到的路徑

分界點在之前掃描過的路徑經過

對于情況$1$我們有數組$b_i$表示在根到該節點的路徑中是否存在長度為$i$的邊，然后用$g{2}_i$表示之前掃描過的子樹中存在多少長度為$i$的路徑且中間沒有分界點(這里的分界點指的是有一個點的$d_i$等于它的$d_i$)。

對于情況$2$我們用$g_i$表示之前的子樹中存在多少長度為$i$的路徑且中間有分界點(這里的概念同上)。

然后每次進行兩次$dfs$，一次統計$ans$，一次修改$g$和$g2$即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+1,M=N*2; struct Edge_node{int to,next,w; }a[M]; int n,m,ls[N],siz[N],f[M],g[M],g2[M]; int b[M],tot,num,root,maxs,mins,sum; long long ans; bool v[N]; void addl(int x,int y,int w) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w*2-1; } void groot(int x,int fa) {siz[x]=1;f[x]=0;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa||v[y]) continue;groot(y,x);siz[x]+=siz[y];f[x]=max(f[x],siz[y]);}f[x]=max(f[x],num-f[x]);if(f[x]<f[root]) root=x; } void dfs(int x,int fa,int w) {maxs=max(maxs,w);mins=min(mins,w);ans+=g[M-w];if(b[w]) ans+=(long long)g2[M-w];if(w==N) ans+=(long long)(b[w]>1);b[w]++;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(v[y]||y==fa) continue;dfs(y,x,w+a[i].w);;}b[w]--; } void Change(int x,int fa,int w) {++(b[w]?g[w]:g2[w]);b[w]++;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(v[y]||y==fa) continue;Change(y,x,w+a[i].w);}b[w]--; } void solve(int x) {v[x]=1;int y;b[mins=maxs=N]=1; for(int i=ls[x];i;i=a[i].next)if(!v[y=a[i].to])dfs(y,x,N+a[i].w),Change(y,x,N+a[i].w);memset(g+mins,0,(maxs-mins+1)<<2);memset(g2+mins,0,(maxs-mins+1)<<2);for(int i=ls[x];i;i=a[i].next)if(!v[y=a[i].to])root=0,groot(y,x),num=siz[y],solve(root); } int main() {scanf("%d",&n);for(int i=1;i<n;i++){int x,y,w;scanf("%d%d%d",&x,&y,&w);addl(x,y,w);addl(y,x,w);}f[0]=2147483647;num=n;groot(1,1);solve(root);printf("%lld",ans); }

總結

以上是生活随笔為你收集整理的P3085,jzoj3234-[USACO13OPEN]阴和阳【点分治】的全部內容，希望文章能夠幫你解決所遇到的問題。

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