【APIO2018】铁人两项

2021-06-11 06:03

阅读：590

标签：turn fine ++i 存在 out ++ tar lin math

【APIO2018】铁人两项

题目描述

大意就是给定一张无向图，询问三元组\((s,c,f)\)中满足\(s\neq c\neq f\)且存在\((s\to c\to f)\)的简单路径（每个点最多经过一次）的数量。

\(1\leq n,\leq 10^5,1\leq m\leq 2*10^5\)

我们考虑枚举\(s,f\)然后计算中间\(c\)的数量。我们发现对于一张图上统计两点之间路径上的点数量很好做。于是我们考虑建圆方树。

我们将圆点的权值定为\(-1\)，将方点的权值定为与其直接相连的圆点的数量。\(u\)到\(v\)路径上可能经过的点的数量就是圆方树上\(u\to v\)路径上除了\(u,v\)的点权之和\(-2\)。

于是我们用树形\(\text{DP}\)，计算每个点对答案的贡献。

代码：

#include
#define ll long long
#define N 200005

using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch'9') {if(ch=='-') f=-1;ch=getchar();}while('0'=dfn[v]) {
                work(v,to);
            }
        } else low[v]=min(low[v],dfn[to]);
    }
}

ll ans;
int size[N];
void dfs(int v) {
    int tim=0;
    for(int i=g.h[v];i;i=g.nxt[i]) {
        int to=g.to[i];
        dfs(to);
        ans+=1ll*val[v]*size[v]*size[to];
        tim+=size[v]*size[to];
        size[v]+=size[to];
    }
    if(v

【APIO2018】铁人两项

标签：turn fine ++i 存在 out ++ tar lin math

原文地址：https://www.cnblogs.com/hchhch233/p/10574714.html

上一篇：LoadRunner监控windows资源报错Monitor name :Windows Resources. Cannot connect to machine

下一篇：【原】无脑操作：Windows下搭建Kafka运行环境

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：【APIO2018】铁人两项
文章链接：http://soscw.com/essay/93468.html

亲，登录后才可以留言！

【APIO2018】铁人两项

【APIO2018】铁人两项

评论

热门文章

推荐文章

最新文章

置顶文章