文章目錄

• 題意：
• 思路：

傳送門

題意：

給你一顆$n$個(gè)點(diǎn)的樹，每條邊為黑色或者白色，問滿足以下條件的路徑條數(shù)：路徑上存在一個(gè)不是端點(diǎn)的點(diǎn)，使得兩端點(diǎn)到該點(diǎn)的兩條路徑上兩種顏色的邊數(shù)相等。

$1\le n\le 100000$

思路：

統(tǒng)計(jì)樹上路徑問題顯然需要用到點(diǎn)分治了，這個(gè)題維護(hù)的信息比較麻煩，想明白了思路還需要考慮如何做才能使代碼變得簡(jiǎn)便好寫。

考慮點(diǎn)分治每個(gè)步驟需要算的貢獻(xiàn)，在選出重心之后，之后的子樹中就不會(huì)包含重心這個(gè)點(diǎn)，所以貢獻(xiàn)需要算每顆包含重心的子樹內(nèi)的路徑以及這些子樹之間構(gòu)成的路徑的貢獻(xiàn)，一定不要忘記算包含重心的子樹貢獻(xiàn)，我由于忘記了調(diào)了一年。。

讓后就是遍歷每顆子樹了，將$0$看成$?1$，我們記三個(gè)變量，從重心到當(dāng)前點(diǎn)的前綴和，這樣就可以判斷這個(gè)點(diǎn)到重心的路徑上是否有一段和為0了，讓后再用數(shù)組記一下有多少從重心開始的路徑和為$x$，即$mp[x][0]$，讓后如果第一個(gè)變量大于$0$的話，那么也讓$mp[x][1]++$。這個(gè)時(shí)候統(tǒng)計(jì)貢獻(xiàn)就比較容易了，當(dāng)有一段和為$0$的時(shí)候，此時(shí)假設(shè)前綴和是$x$，那么加上$mp[x][0]$即可，否則加上$mp[x][1]$。讓后一顆包含重心的子樹內(nèi)自己貢獻(xiàn)的話就是有兩段和為$0$，并且當(dāng)前這個(gè)點(diǎn)的前綴和為$0$，讓答案加$1$即可。

#include<bits/stdc++.h> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define Mid (tr[u].l+tr[u].r>>1) #define pb push_back using namespace std;const int N=201000,INF=0x3f3f3f3f,mod=1e9+7,P=100000; typedef long long LL; typedef pair<int,int> PII;int n,k; vector<PII>v[N]; vector<int>q,qt; bool st[N]; int mp[N][2],dis[N]; vector<int>all;int get_size(int u,int f) {if(st[u]) return 0;int ans=1;for(auto x:v[u]) if(x.X!=f) {ans+=get_size(x.X,u);}return ans; }int get_wc(int u,int f,int tot,int &wc) {if(st[u]) return 0;int sum=1,mx=0;for(auto x:v[u]) {if(x.X==f) continue;int now=get_wc(x.X,u,tot,wc);mx=max(mx,now); sum+=now;}mx=max(mx,tot-sum);if(mx<=tot/2) wc=u;return sum; }LL get_dis_ans(int u,int f,int w) {if(st[u]) return 0;LL ans=0;if(dis[w+P]) {ans+=mp[P-w][0];if(w==0&&dis[P]>=2) ans++;} else ans+=mp[P-w][1];dis[w+P]++;for(auto x:v[u]) {if(x.X==f) continue;ans+=get_dis_ans(x.X,u,w+x.Y);}dis[w+P]--;return ans; }void get_dis(int u,int f,int w) {if(st[u]) return;mp[w+P][0]++;if(dis[w+P]>0) {mp[w+P][1]++;}all.pb(w+P);dis[w+P]++;for(auto x:v[u]) {if(x.X==f) continue;get_dis(x.X,u,w+x.Y);}dis[w+P]--; }LL calc(int u) {if(st[u]) return 0;get_wc(u,-1,get_size(u,-1),u);LL ans=0; st[u]=true;for(auto x:v[u]) {ans+=get_dis_ans(x.X,-1,x.Y);get_dis(x.X,-1,x.Y);}for(auto x:all) mp[x][0]=mp[x][1]=0;all.clear();for(auto x:v[u]) ans+=calc(x.X);return ans; }void solve() {scanf("%d",&n);dis[P]=1;for(int i=1;i<=n-1;i++) {int a,b,c; scanf("%d%d%d",&a,&b,&c);if(c==0) c=-1;v[a].pb({b,c});v[b].pb({a,c});}printf("%lld\n",calc(1)); }int main() {int _=1;while(_--) {solve();}return 0; } /* 5 1 2 1 1 3 0 3 4 0 4 5 1 */

總結(jié)

以上是生活随笔為你收集整理的P3085 [USACO13OPEN]Yin and Yang G 点分治的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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