电压机制（树上差分）

树上差分）"/>

电压机制（树上差分）

电压机制(voltage)
【问题描述】
科学家在“无限神机”（Infinity Machine）找到一个奇怪的机制，这个机制有N个元件，有M条电线连接这些元件，所有元件都是连通的。两个元件之间可能有多条电线连接。
科学家对这些元件可以任意地设置为“高电压”和“低电压”两种模式，如果一条电线的一端为高电压，另一端为低电压，这条电线就会产生电流。
为了安全的研究“无限神机”，科学家需要找到一条电线，将它的两端设为相同的电压，并且除选择的这条电线外，其它所有电线都有电流（否则就没有研究的价值了）。
有多少条电线满足这样的条件？
【输入格式】
从文件 voltage.in 中读入数据。
输入的第一行包含两个正整数 n, m ,表示元件数和电线数。
接下来 m 行，每行两个整数 u, v，表示元件 u 和元件 v 有一条电线连接
【输出格式】
输出到文件 voltage.out 中。
输出一个整数，表示有多少条电线满足条件。
【样例1输入】
4 5
1 2
1 3
1 4
2 4
3 4
【样例1输出】

1

不存在环时，就是树边数；

存在环时：

如果奇数环上的边必须选一条把两端电压设为相等，偶数环上任意的边不可以把电压设为相等

其实这道题求的是所有奇数环都包含的公共边中不被偶数环包含的边数。

建一棵树，多余的边视为非树边。

知道两性质：
1.有多条非树边和树边组成的不同奇环，那么任意一条非树边一定不可能在所有奇环上，那么非树边不可能是满足条件的边

2.如果两条非树边和其他树边构成环，这种环是没有用的

构成一、两个奇环（1，2，3），（1，2，3，4，5），偶环上的边没用（2，3，4，5），不考虑两条，只要边2，3有用

构成两个偶环（1，3，5，2），（1，3，5，7，4，2），都没用。不考虑两条

构成一奇一偶（1，2，3，4，5，6，7），（1，2，3，5），形成奇环（2，4，5，6，7），树边原来就在奇环上。和分开来考虑是一样的

这个奇环

6，7边是有用的，根据性质一来判定。

综上所述，可以一条一条的考虑非树边=、=。

只有返祖边才有贡献。

利用边权下放点权

联想一下把(u,v)两点间的路径都加1，是怎么利用差分。

点u的子树和表示u-fa[u]这条边被经过几次

1.找到两点的lca;

2.u点+1，v点加1，lca减2;

同理，如果u有一条返祖边到v

那么v其实就是u的祖先。

那么u+1，v-1；就好。

其实u，v在同一个环，环大小为dep[u]-dep[v] + 1;

因为我们要统计一条边被奇环，和偶环包含的次数。

所以要分开算。

差分的时候和统计的时候建的树要一样。遍历边的顺寻一样。（一定要注意啊啊！所以记录的是从哪条边来的，而不是fa是谁，因为它和它的fa之间有可能有多条边=。=、）

只要一条边满足被所有的奇环包含。并不被任意一个偶环包含。那么ans++；

最后根据性质一。

判一下是不是只有一个奇环，是则ans++。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int tp = 1, nex[500005], h[100005], tov[500005], fa[100005];
int vis[100005], dep[100005], jihuan, ouhuan, ji[100005], ou[100005],visb[500005];
void add(int x, int y)
{tp++;nex[tp] = h[x];tov[tp] = y;h[x] = tp;
}
void dfs(int x, int bi)
{for(int i = h[x]; i; i = nex[i]){if(visb[i] == 1) continue;visb[i] = visb[i^1] = 1;int v = tov[i];if(vis[v]){int ha = dep[x] - dep[v];if(ha % 2 == 0){ji[v] --;ji[x] ++;jihuan++;} else{ou[v] --;ou[x] ++;ouhuan++; }	}else{vis[v] = 1;dep[v] = dep[x] + 1; fa[v] = i;dfs(v,i);}}
}
void dfs1(int x, int f)
{for(int i = h[x]; i; i = nex[i]){int v = tov[i];if(fa[v] == i){dfs1(v,x);ji[x] += ji[v];ou[x] += ou[v];	}}
}
int main()
{freopen("voltage.in","r",stdin);freopen("voltage.out","w",stdout);scanf("%d%d",&n, &m);for(int i = 1; i <= m; i++){int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);}for(int i = 1; i <= n; i++)if(vis[i] == 0){vis[i] = 1;dfs(i, tp +4);} for(int i = 1; i <= n; i++){if(fa[i] == 0)	dfs1(i, 0);}//一定要记边啊，它和它的父亲有很多边啊。 int ans = 0;for(int i = 1; i <= n; i++){if(fa[i] != 0 && ji[i] == jihuan && ou[i] == 0){ans ++;}}if(jihuan == 1) ans++;cout << ans;return 0;
}