test20181016 B君的第三题

时间：2023-03-09 16:14:25
test20181016 B君的第三题

题意

B 君的第三题(haskell)

题目描述

大学四年，我为什么，为什么不好好读书，没找到和你一样的工作。

B 君某天看到了这样一个题，勾起了无穷的回忆。

输入\(n, k\) 和一棵\(n\) 个点的树，有边权，没有点权。两点\(i, j\) 之间的距离\(D(i, j)\) 定义为路径上的边权和。求

\[\sum_{1 \leq i < j \leq n} \left\lceil \frac{D(i,j)}{k} \right\rceil
\]

换句话说，枚举无序的两个点，求出距离除以\(k\) 上取整的和。

输入格式

输入第一行包含两个整数\(n, k\)。

接下来\(n-1\) 行，每行三个整数\(x, y, z\)，表示\(x\) 和\(y\) 之间有一条边，边权为\(z\)。

输出格式

输出一行一个整数，表示答案。

样例输入

4 6

1 2 2

1 3 3

1 4 4

样例输出

7

数据规模与约定

对于100% 的数据，满足\(1 \leq n \leq 100000, 1 \leq k \leq 10\)。

对于100% 的数据，满足\(1 \leq x, y \leq n, 1 \leq z \leq 10\)。

对于30% 的数据，满足\(n \leq 1000\)。

对于另20% 的数据，满足\(k = 1\)。

对于另20% 的数据，满足\(k = 2\)。

分析

先考虑没有取整的情况，是一个经典题。

然后考虑有多少条路径模 k 余 1, 2, . . .。

这题是NOI2011道路修建和BZOJ2152聪聪可可改编而成的一道好题。

\[\lceil \frac{x}{k} \rceil = \frac{x + k - x \mod{k}}{k}
\]

所以我们需要求出分别有多少路径模k等于1,2,..k-1。

考虑dp。

用\(f(i,j)\)表示i的子树中有多少点到i的距离mod k = j，\(c(i)\)表示全局有多少路径mod k = i。

f、c都能在dfs的时候求出，注意顺序，不能用子树乘自己本身的方案。

代码

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iostream>

#include<string>

#include<vector>

#include<list>

#include<deque>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<algorithm>

#include<complex>

#define rg register

#define il inline

#define co const

#pragma GCC optimize ("O0")

using namespace std;

template<class T> il T read(rg T&x)

{

    rg T data=0;

	rg int w=1;

    rg char ch=getchar();

    while(!isdigit(ch))

    {

		if(ch=='-')

			w=-1;

		ch=getchar();

	}

    while(isdigit(ch))

        data=10*data+ch-'0',ch=getchar();

    return x=data*w;

}

typedef long long ll;

const int INF=0x7fffffff;

const int MAXN=1e5+7,MAXK=11;

int n,k;

struct Edge

{

	int nx,to,w;

}E[MAXN<<1];

int head[MAXN],ecnt;

void addedge(rg int x,rg int y,rg int w)

{

	E[++ecnt].to=y,E[ecnt].w=w;

	E[ecnt].nx=head[x],head[x]=ecnt;

}

int siz[MAXN];

int f[MAXN][MAXK];

ll c[MAXN];

ll ans;

il void dfs(rg int x,rg int fa)

{

	siz[x]=1;

	f[x][0]=1;

	for(rg int i=head[x];i;i=E[i].nx)

	{

		rg int y=E[i].to,w=E[i].w;

		if(y==fa)

			continue;

		dfs(y,x);

		siz[x]+=siz[y];

		ans += (ll) (n - siz[y]) * siz[y] * w;

		for(rg int p=0;p<k;++p)

			for(rg int q=0;q<k;++q)

				c[(p + q + w) % k] += f[x][p] * f[y][q];

		for(rg int j=0;j<k;++j)

			f[x][(j + w) % k] += f[y][j];

	}

}

int main()

{

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

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

	read(n);read(k);

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

	{

		rg int x,y,w;

		read(x);read(y);read(w);

		addedge(x,y,w);

		addedge(y,x,w);

	}

	dfs(1,0);

	for(rg int i=1;i<k;++i)

	{

		ans += (k-i) * c[i];

	}

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

//  fclose(stdin);

//  fclose(stdout);

    return 0;

}

相关文章