BZOJ 4543 2016北京集训测试赛（二）Problem B: thr

Solution

这题的解法很妙啊... 考虑这三个点可能的形态: 令它们的重心为距离到这三个点都相同的节点, 则其中两个点分别在重心的两棵子树中, 且到重心的距离相等; 第三个点可能在重心的一棵不同于前两个点子树上, 也有可能在重心往上走可以到达的位置上.

定义数组\(f[i][j]\)表示在以\(i\)为根的子树下与\(i\)的距离为\(j\)的节点个数; \(g[i][j]\)表示在以\(i\)为根的子树下, 有多少个点对满足如下条件: 这个点对到它们LCA的距离相同, 我们假设其为\(d\), 则\(i\)到它们的LCA的距离为\(d - i\), 也就是说, 假如这两个点要找到一个在\(i\)上方的第三个点组成一组答案, 则第三个点到\(i\)的距离为\(j\).

考虑枚举每个点作为重心的情况. 进行一次DFS, 令\(u\)为当前点, \(v\)为\(u\)的一个子节点, 则有:

\[ans += \sum_i g[u][i] \times f[v][i - 1] + g[v][i] \times f[u][i - 1] \\
g[u][i] += g[v][i + 1] + f[u][i] \times f[v][i - 1] \\
f[u][i] += f[v][i - 1] \\
\]

然后我们发现这种方法的转移是\(O(n^2)\)的... 考虑如何优化: 我们注意到, 当一个点\(u\)计算其第一个子节点时, 可以直接将\(f[u][i]\)赋值为\(f[v][i - 1]\), \(g[u][i]\)赋值为\(g[v][i + 1]\), 因此在计算完这个子节点后, 直接对返回的数组指针进行位移就可以得到当前点的\(f\)和\(g\). 因此考虑采用按深度树链剖分的方法, 从重儿子处继承\(f\)和\(g\)数组.

时间复杂度: \(O(n)\). 为什么? 不会证. 以后学了长链剖分再填坑吧.

由于数组是动态开的, 同时还存在指针变化的操作, 因此边界可能比较难计算. 假如你比较懒, 就直接将数组大小/对答案贡献的范围调大一些, 这样可以省去不少麻烦.

#include <cstdio>

#include <cctype>

#include <vector>

#include <algorithm>

#include <cstring>

namespace Zeonfai

{

	inline int getInt()

	{

		int a = 0, sgn = 1;

		char c;

		while(! isdigit(c = getchar())) if(c == '-') sgn *= -1;

		while(isdigit(c)) a = a * 10 + c - '0', c = getchar();

		return a * sgn;

	}

}

const int N = (int)5e4;

int n;

struct result

{

    long long *first, *second;

    inline result() {}

    inline result(long long *_first, long long *_second)

    {

    	first = _first; second = _second;

	}

};

long long ans;

struct tree

{

    struct node

    {

        std::vector<node*> edg;

        int maxDepth, dep;

        node *hvy;

        inline void clear()

        {

            edg.clear(); hvy = NULL;

        }

    }nd[N + 1];

    inline void clear()

    {

    	for(int i = 1; i <= n; ++ i) nd[i].clear();

	}

    inline void addEdge(int u, int v)

    {

        nd[u].edg.push_back(nd + v); nd[v].edg.push_back(nd + u);

    }

    void getDepth(node *u, node *pre)

    {

        u->maxDepth = u->dep = pre == NULL ? 0 : pre->dep + 1;

        for(auto v : u->edg) if(v != pre)

        {

            getDepth(v, u); u->maxDepth = std::max(u->maxDepth, v->maxDepth);

            if(u->hvy == NULL || v->maxDepth > u->hvy->maxDepth) u->hvy = v;

        }

    }

    result decomposition(node *u, node *pre, node *tp)

    {

        result res;

    	long long *f, *g;

        if(u->hvy != NULL) res = decomposition(u->hvy, u, tp), f = res.first - 1, g = res.second + 1;

        else

		{

			int len = u->dep - tp->dep + 10; //懒得想边界了, 直接开大一些, 求对答案的时候也求多一些就可以了

			f = new long long[len << 1]; memset(f, 0, len << 1 << 3); f += len;

			g = new long long[len << 1]; memset(g, 0, len << 1 << 3);

		}

        f[0] = 1; ans += g[0];

        for(auto v : u->edg) if(v != pre && v != u->hvy)

        {

        	int len = v->maxDepth - v->dep + 1;

        	res = decomposition(v, u, v); long long *_f = res.first, *_g = res.second;

			for(int i = 1; i <= len; ++ i) ans += g[i] * _f[i - 1] + _g[i] * f[i - 1];

			for(int i = 1; i <= len; ++ i) g[i] += _f[i - 1] * f[i];

			for(int i = 0; i <= len; ++ i) g[i] += _g[i + 1];

			for(int i = 1; i <= len; ++ i) f[i] += _f[i - 1];

		}

		return result(f, g);

    }

}T;

int main()

{

	#ifndef ONLINE_JUDGE

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

	freopen("thr.out", "w", stdout);

	#endif

    using namespace Zeonfai;

    while(n = getInt())

    {

    	T.clear();

	    for(int i = 1; i < n; ++ i)

	    {

	        int u = getInt(), v = getInt();

	        T.addEdge(u, v);

	    }

	    T.getDepth(T.nd + 1, NULL);

	    ans = 0;

	    T.decomposition(T.nd + 1, NULL, T.nd + 1);

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

	}

}

巴特西

BZOJ 4543 2016北京集训测试赛（二）Problem B: thr

Solution

最新文章

热门文章