标签：cto   c++   continue   can   mat   int   取值   lld   typedef   

II.[APIO2018] Duathlon 铁人两项

我们考虑对于这样一个三元组\(\left\)，假如我们固定了\(s\)和\(f\)，\(c\)有多少种可能的取值呢？

显然，\(c\)的取值等于\(s\rightarrow f\)的简单路径的并集的大小减\(2\)，因为\(s\)和\(f\)不能作为\(c\)。

那这个并集的大小呢？

我们先假设\(s\)与\(f\)位于同一个点双里面，则它们之间必定存在一条路径经过任何一个点\(c\)。故实际上并集大小就是点双大小。

现在它们不在同一个点双中，则并集大小则为一路上经过的所有点双的大小之和，减去割点的大小（它们被包括在两个点双之中），再减去\(2\)。

则我们发现，如果将方点的点权赋为它代表的点双的大小，圆点的点权赋为\(-1\)，则圆方树上\(s\rightarrow f\)路径上所有点权之和，就等于（并集大小减二）。

因此我们实际上要求的就是所有不同的圆点点对间点权之和。

我们考虑对于路径上的一个点\(c\)，它究竟被包含到多少条路径中即可。这个简单DP一下就行了。

注意这里的路径是有向路径，故记得乘二。

代码：

#include
using namespace std;
typedef long long ll;
ll res;
int n,m,c,all;
namespace RST{
	vectorv[200100];
	int val[200100],sz[200100];
	void dfs(int x,int fa){
		sz[x]=(xv[100100];
	int dfn[100100],low[100100],tot;
	stacks;
	void Tarjan(int x){
		all++;
		dfn[x]=low[x]=++tot,s.push(x);
		for(auto y:v[x]){
			if(!dfn[y]){
				Tarjan(y),low[x]=min(low[x],low[y]);
				if(low[y]>=dfn[x]){
					c++;
					while(s.top()!=y)RST::ae(c,s.top()),s.pop();
					RST::ae(c,s.top()),s.pop();
					RST::ae(c,x);
				}
			}else low[x]=min(low[x],dfn[y]);
		}
	}
}
int main(){
	scanf("%d%d",&n,&m),c=n;
	for(int i=1,x,y;i

[APIO2018] Duathlon 铁人两项

标签：cto   c++   continue   can   mat   int   取值   lld   typedef   

原文地址：https://www.cnblogs.com/Troverld/p/14621498.html