題目鏈接：點擊查看

題目大意：給出一棵 $n$ 個點的樹，再給出 $m$ 條路徑，現(xiàn)在問有多少個路徑對 $(x,y)$，滿足第 $x$ 條路徑和第 $y$ 條路徑有且僅有一個交點

題目分析：參考至大佬博客：https://www.cnblogs.com/syksykCCC/p/CF1486F.html

再借個圖。。（侵權(quán)刪）

本題需要求的路徑只有可能是上述兩種情況，第一種是 $LCA$ 相同，第二種是 $LCA$ 不同，不過總而言之都需要利用 $LCA$ 來輔助計數(shù)

感覺是挺套路的題，直接說做法吧，對于每條路徑，我們將其抽象成五個變量即可：$u,v,a,b,lca$

其中 $u,v,lca$ 顧名思義且很好求，就是路徑兩端的節(jié)點以及 $LCA(u,v)$，$a,b$ 儲存的是點 $u$ 和 $v$ 分別在 $lca$ 的哪棵子樹中，我們只需要保存一下從 $lca$ 到 $u$ 這條路徑上的第一個節(jié)點就可以了，這個用倍增也很容易求，就是需要注意一下，假如 $u$ 和 $lca$ 是同一個點的情況，此時用 $?1$ 來表示這條路徑，這里的 $a,b$ 是輔助計數(shù)用的

為了防止重復(fù)計數(shù)，我們還需要最后令 $(a,b)$ 二元對滿足 $a<=b$

現(xiàn)在開始討論如何計數(shù)，對于第一種情況比較簡單，當(dāng) $lca$ 確定時，我們只需要求 $(a,b)$ 二元對互不相同的對數(shù)即可，容斥一下就好了：$cn{t}_{(a,b)互不相同}=(總對數(shù))?cn{t}_{a相同}?cn{t}_{b相同}+cn{t}_{(a,b)相同}$

對于第二種情況，我們其實只需要統(tǒng)計一下除去 $a$ 和 $b$ 的子樹后， $lca$ 的子樹中有多少個路徑的端點即可，為了做到不重不漏，需要先統(tǒng)計深度較小的 $lca$ 然后再統(tǒng)計深度較大的，正確性顯然，手玩一下就能明白了

最后就是實現(xiàn)了，第一種情況的計數(shù)，只需要開個 $map$ 就好了，第二種情況的統(tǒng)計子樹，維護一下 $dfs$ 序然后用樹狀數(shù)組維護實現(xiàn)起來也是比較簡單

代碼：

// Problem: F. Pairs of Paths // Contest: Codeforces - Codeforces Round #703 (Div. 2) // URL: https://codeforces.com/contest/1486/problem/F // Memory Limit: 512 MB // Time Limit: 6000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=3e5+100; vector<int>node[N]; int dp[N][25],deep[N],L[N],R[N],dfn=0; int c[N]; struct Path {int u,v,a,b,lca;bool operator<(const Path& t) const {if(deep[lca]!=deep[t.lca]) {return deep[lca]<deep[t.lca];}return lca<t.lca;} }p[N]; void dfs(int u,int fa,int dep) {L[u]=++dfn;deep[u]=dep;dp[u][0]=fa;for(int i=1;i<=20;i++) {dp[u][i]=dp[dp[u][i-1]][i-1];}for(auto v:node[u]) {if(v==fa) {continue;}dfs(v,u,dep+1);}R[u]=dfn; } int get_fa(int u,int x) {if(x>=0) {for(int i=0;i<=20;i++) {if((x>>i)&1) {u=dp[u][i];}}}return u; } int LCA(int x,int y) {if(deep[x]<deep[y]) {swap(x,y);}for(int i=20;i>=0;i--) {if(deep[x]-deep[y]>=(1<<i)) {x=dp[x][i];}}if(x==y) {return x;}for(int i=20;i>=0;i--) {if(dp[x][i]!=dp[y][i]) {x=dp[x][i];y=dp[y][i];}}return dp[x][0]; } void add(int x) {for(int i=x;i<N;i+=lowbit(i)) {c[i]++;} } int ask(int x) {int ans=0;for(int i=x;i>0;i-=lowbit(i)) {ans+=c[i];}return ans; } int query(int l,int r) {return ask(r)-ask(l-1); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;read(n);for(int i=1;i<n;i++) {int u,v;read(u),read(v);node[u].push_back(v);node[v].push_back(u);}dfs(1,0,0);int m;read(m);for(int i=1;i<=m;i++) {read(p[i].u),read(p[i].v);int u=p[i].u,v=p[i].v;int lca=LCA(u,v);p[i].lca=lca;int fu=get_fa(u,deep[u]-deep[lca]-1);int fv=get_fa(v,deep[v]-deep[lca]-1);p[i].a=(lca==fu)?-1:fu;p[i].b=(lca==fv)?-1:fv;if(p[i].a>p[i].b) {swap(p[i].a,p[i].b);}}sort(p+1,p+1+m);LL ans1=0,ans2=0;for(int i=1;i<=m;i++) {int j=i;while(p[i].lca==p[j].lca) {j++;}map<int,int>cnt1;map<pair<int,int>,int>cnt2;for(int k=i;k<j;k++) {//[i,j) lca is sameint lca=p[k].lca,a=p[k].a,b=p[k].b;ans1+=(k-i);if(a!=-1) {ans1-=cnt1[a];cnt1[a]++;}if(b!=-1) {ans1-=cnt1[b];cnt1[b]++;}if(a!=-1&&b!=-1) {ans1+=cnt2[{a,b}];cnt2[{a,b}]++;}ans2+=query(L[lca],R[lca]);if(a!=-1) {ans2-=query(L[a],R[a]);}if(b!=-1) {ans2-=query(L[b],R[b]);}}for(int k=i;k<j;k++) {add(L[p[k].u]),add(L[p[k].v]);}i=j-1;}cout<<ans1+ans2<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1486F Pairs of Paths(树上计数+容斥)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。