Description

采藥人的藥田是一個樹狀結(jié)構(gòu)，每條路徑上都種植著同種藥材。
采藥人以自己對藥材獨到的見解，對每種藥材進行了分類。大致分為兩類，一種是陰性的，一種是陽性的。
采藥人每天都要進行采藥活動。他選擇的路徑是很有講究的，他認為陰陽平衡是很重要的，所以他走的一定是兩種藥材數(shù)目相等的路徑。采藥工作是很辛苦的，所以他希望他選出的路徑中有一個可以作為休息站的節(jié)點（不包括起點和終點），滿足起點到休息站和休息站到終點的路徑也是陰陽平衡的。他想知道他一共可以選擇多少種不同的路徑。

Input

第1行包含一個整數(shù)N。
接下來N-1行，每行包含三個整數(shù)a_i、b_i和t_i，表示這條路上藥材的類型。

Output

輸出符合采藥人要求的路徑數(shù)目。

Sample Input

7
1 2 0
3 1 1
2 4 0
5 2 0
6 3 1
5 7 1

Sample Output

1

HINT

?

對于100%的數(shù)據(jù)，N ≤ 100,000。

這題就惡心了呀 還是點分治 考慮經(jīng)過點x的路徑，f[i][0/1]表示當前子樹到根的路徑為i,存在/不存在休息點的方案數(shù),g[i][0/1]表示前幾棵子樹到根的路徑為i,存在/不存在休息點的方案數(shù) 那么對于一個子樹，它對答案的貢獻是f[0][0]*g[0][0]+Σf[i][0]*g[-i][1]+f[i][1]*g[-i][0]+f[i][1]*g[-i][1] 第一維搞去掉負數(shù)調(diào)了半天…… #include<cstdio> #include<iostream> #define N 200010 #define LL long long using namespace std; inline int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } struct edge{int to,next,v;}e[2*N]; int head[N],son[N],f[N],mrk[N],dep[N]; LL s[2*N][2],t[2*N][2],dis[N]; int n,cnt,root,sum,mxd; bool vis[N]; LL ans; inline void ins(int u,int v,int w) {e[++cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt; } inline void insert(int u,int v,int w) {ins(u,v,w);ins(v,u,w); } inline void getroot(int x,int fa) {son[x]=1;f[x]=0;for (int i=head[x];i;i=e[i].next)if (!vis[e[i].to]&&fa!=e[i].to){getroot(e[i].to,x);son[x]+=son[e[i].to];f[x]=max(f[x],son[e[i].to]);}f[x]=max(f[x],sum-son[x]);if (f[x]<f[root])root=x; } inline void dfs(int x,int fa) {mxd=max(mxd,dep[x]);if (mrk[dis[x]])s[dis[x]][1]++;else s[dis[x]][0]++;mrk[dis[x]]++;for(int i=head[x];i;i=e[i].next)if (!vis[e[i].to]&&fa!=e[i].to){dep[e[i].to]=dep[x]+1;dis[e[i].to]=dis[x]+e[i].v;dfs(e[i].to,x);}mrk[dis[x]]--; } inline void calc(int x) {int mx=0;t[n][0]=1;for (int i=head[x];i;i=e[i].next)if (!vis[e[i].to]){dis[e[i].to]=n+e[i].v;dep[e[i].to]=1;mxd=1;dfs(e[i].to,0);mx=max(mx,mxd);ans+=(t[n][0]-1)*s[n][0];for (int j=-mxd;j<=mxd;j++)ans+=t[n-j][1]*s[n+j][1]+t[n-j][0]*s[n+j][1]+t[n-j][1]*s[n+j][0];for (int j=n-mxd;j<=n+mxd;j++){t[j][0]+=s[j][0];t[j][1]+=s[j][1];s[j][0]=s[j][1]=0;}}for (int i=n-mx;i<=n+mx;i++)t[i][0]=t[i][1]=0; } inline void solve(int x) {vis[x]=1;calc(x);for (int i=head[x];i;i=e[i].next)if (!vis[e[i].to]){sum=son[e[i].to]; root=0;getroot(e[i].to,0);solve(root);} } int main() {n=read();for (int i=1;i<n;i++){int x=read(),y=read(),z=read();if (!z)z--;insert(x,y,z);}f[0]=n+1;sum=n;getroot(1,0);solve(root);printf("%lld\n",ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zhber/p/4216245.html

總結(jié)

以上是生活随笔為你收集整理的bzoj3697 采药人的路径的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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