正題

---

題目大意

一棵樹
若干條路徑，哪個點經過的路徑最多，求路徑條數。

---

解題思路

對于每條路徑計算一次$LCA$，然后樹上差分就好了。

---

$code$

#include<cstdio> #include<queue> #include<cmath> using namespace std; const int N=50010; struct node{int to,next; }a[N*2]; int tot,ls[N],dep[N],f[N][20],c[N]; int y,n,k,t,ans; queue<int> q; void addl(int x,int y) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } void bfs() {t=(int)(log(n)/log(2))+1;q.push(1);dep[1]=1;while(!q.empty()){int x=q.front();q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(dep[y]) continue;dep[y]=dep[x]+1;f[y][0]=x;q.push(y);}}for(int j=1;j<=t;j++)for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1]; } int LCA(int x,int y) {if(dep[x]>dep[y]) swap(x,y);for(int i=t;i>=0;i--)if(dep[f[y][i]]>=dep[x])y=f[y][i];if(x==y) return x;for(int i=t;i>=0;i--)if(f[y][i]!=f[x][i]){y=f[y][i];x=f[x][i];}return f[x][0]; } void get_ans(int x) {for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(dep[x]+1!=dep[y]) continue;get_ans(y);c[x]+=c[y];}ans=max(ans,c[x]); } int main() {scanf("%d%d",&n,&k);for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y);addl(y,x);}bfs();for(int i=1;i<=k;i++){int s,e,lca;scanf("%d%d",&s,&e);lca=LCA(s,e);c[s]++;c[e]++;c[lca]--;c[f[lca][0]]--;}get_ans(1);printf("%d",ans); }

總結

以上是生活随笔為你收集整理的P3128-最大流Max Flow【树上差分,LCA】的全部內容，希望文章能夠幫你解決所遇到的問題。

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