网页ui设计网站,二手书网站建设报告,后台控制网站关键词设置的详细代码,用dw做网站导航的步骤题意#xff1a;给一张 nnn 点 mmm 边的简单无向图#xff0c;求有多少个三元组 (s,c,f)(s,c,f)(s,c,f) #xff0c;满足存在一条从 sss 到 fff 经过 ccc 的简单路径。 n≤105,m≤2105n\leq 10^5,m\leq 2\times 10^5n≤105,m≤2105
首先这个 “经过 ccc 的简单路径” …题意给一张 nnn 点 mmm 边的简单无向图求有多少个三元组 (s,c,f)(s,c,f)(s,c,f) 满足存在一条从 sss 到 fff 经过 ccc 的简单路径。
n≤105,m≤2×105n\leq 10^5,m\leq 2\times 10^5n≤105,m≤2×105
首先这个 “经过 ccc 的简单路径” 即 ccc 取所有 sss 到 fff 的简单路径的交集就是能到达的所有点双的并集是圆方树的标志。具体讲解可以参考 PR的博客。
问题转换成了求所有点对路径上的点双的并集的大小 −2-2−2 起始点 之和。
建出圆方树方点权值为其度数 即点双的大小圆点权值为 −1-1−1 点双边界的割点处被统计了两次需要减掉起始点本来就要减掉
这样统计所有圆点路径上的权值之和就可以做到 O(n2)O(n^2)O(n2)
考虑每个结点的贡献计算子树大小方点不算大小瞎算一下就可以 O(n)O(n)O(n)
因为我的板子比较奇怪需要把边去重是 O(nlogn)O(n\log n)O(nlogn) 的
#include iostream
#include cstdio
#include cstring
#include cctype
#include vector
#include algorithm
#define MAXN 100005
#define MAXM 400005
using namespace std;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
struct edge{int u,v;}e[MAXM];
int head[MAXN],nxt[MAXM],cnt1;
inline void addnode(int u,int v)
{e[cnt](edge){u,v};nxt[cnt]head[u];head[u]cnt;
}
int n,m;
int dfn[MAXN],low[MAXN],tim;
int stk[MAXM],tp,vis[MAXM],bcc[MAXM],vcnt;
vectorint rtt[MAXM];
void tarjan(int u)
{dfn[u]low[u]tim;for (int ihead[u];i;inxt[i]){if (!vis[i1]!bcc[i1]) vis[(stk[tp]i)1]1;if (!dfn[e[i].v]){tarjan(e[i].v);low[u]min(low[u],low[e[i].v]);if (dfn[u]low[e[i].v]){rtt[u].push_back(vcnt);rtt[vcnt].push_back(u);while (vis[i1]){int tstk[tp--];vis[t1]0;rtt[bcc[t1]vcnt].push_back(e[t].v);
// rtt[e[t].v].push_back(vcnt);}}}else low[u]min(low[u],dfn[e[i].v]);}
}
int val[MAXM],siz[MAXM];
typedef long long ll;
ll ans;
void dfs(int u,int f,int tot)
{siz[u](un);vis[u]1;for (int i0;i(int)rtt[u].size();i){int vrtt[u][i];if (v!f){dfs(v,u,tot);ans(ll)siz[u]*siz[v]*val[u];siz[u]siz[v];}}ans(ll)siz[u]*(tot-siz[u])*val[u];
}
int main()
{nread(),mread();for (int i1;im;i){int u,v;uread(),vread();addnode(u,v),addnode(v,u);}int las0;vcntn;for (int i1;in;i) if (!dfn[i]) tarjan(i),siz[i]tim-las,lastim;for (int i1;ivcnt;i){sort(rtt[i].begin(),rtt[i].end());rtt[i].erase(unique(rtt[i].begin(),rtt[i].end()),rtt[i].end());}for (int i1;in;i) val[i]-1;for (int in1;ivcnt;i) val[i](int)rtt[i].size();for (int i1;in;i) if (!vis[i]) dfs(i,0,siz[i]);printf(%lld\n,2*ans);return 0;
}
