【LOJ】#2587. 「APIO2018」铁人两项

题解

学习了圆方树！（其实是复习了Tarjan求点双）

我又双叒叕忘记了tarjan点双一个最重要，最重要的事情！

就是……假如low[v] >= dfn[u]，我们就找到了一个点双，开始建立方点，但是，虽然这个点双包括点u，然而这个u啊，它~~很花心~~可能会在很多个点双里！首先u，不能被弹出去

其次呢，在栈里，u和这个点双其他的点，在栈里不一定是连续的一段，一般都是 u （一堆别的点）点双里的点……，所以我们弹出到v，就结束这个点双，然后手动把u加进去

然后我们再来看这道题，我们枚举两个点，起点和终点，能当做中转点的点，一定是路上经过的点双里点的和

那么我们把所有点的值设成-1，方点的值设成点双里点的个数，然后就变成了对圆方树上所有路径统计路径长度，一个优秀做法就是枚举每个点看看会被多少条路径经过

代码

#include <iostream>

#include <cstdio>

#include <vector>

//#define ivorysi

#define pb push_back

#define MAXN 100005

#define space putchar(' ')

#define enter putchar('\n')

using namespace std;

typedef long long int64;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) putchar('-');

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

struct node {

    int to,next;

}E[MAXN * 4];

int N,M,Cnt;

int head[MAXN],sumE,S;

int low[MAXN],dfn[MAXN],idx,sta[MAXN],top,tot,Val[MAXN * 4],siz[MAXN * 4];

int64 ans = 0;

vector<int> son[MAXN * 4];

void add(int u,int v) {

    E[++sumE].to = v;

    E[sumE].next = head[u];

    head[u] = sumE;

}

void Tarjan(int u,int fa) {

    dfn[u] = low[u] = ++idx;

    sta[++top] = u;

    Val[u] = -1;

    siz[u] = 1;

    for(int i = head[u] ; i ; i = E[i].next) {

	int v = E[i].to;

	if(dfn[v] && v != fa) {

	    low[u] = min(dfn[v],low[u]);

	}

	else if(!dfn[v]) {

	    Tarjan(v,u);

	    if(low[v] >= dfn[u]) {

		++Cnt;

		son[u].pb(Cnt);

		while(1) {

		    int x = sta[top--];

		    Val[Cnt]++;

		    son[Cnt].pb(x);

		    siz[Cnt] += siz[x];

		    if(x == v) break;

		}

		Val[Cnt]++;

		siz[u] += siz[Cnt];

	    }

	    else low[u] = min(low[v],low[u]);

	}

    }

}

void dfs(int u) {

    if(Val[u] < 0) ans += (S - 1) * Val[u];

    ans += 1LL * (S - siz[u]) * siz[u] * Val[u];

    for(auto k : son[u]) {

	ans += 1LL * siz[k] * (S - siz[k]) * Val[u];

    }

    for(auto k : son[u]) dfs(k);

}

void Init() {

    read(N);read(M);

    int u,v;

    for(int i = 1 ; i <= M ; ++i) {

	read(u);read(v);

	add(u,v);add(v,u);

    }

    Cnt = N;

}

void Solve() {

    for(int i = 1 ; i <= N ; ++i) {

	if(!dfn[i]) {

	    Tarjan(i,0);

	    S = siz[i];

	    dfs(i);

	}

    }

    printf("%lld\n",ans);

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Init();

    Solve();

    return 0;

}

巴特西

【LOJ】#2587. 「APIO2018」铁人两项

题解

代码

最新文章

热门文章