关键词：
题意
B 君的第三题(haskell)
题目描述
大学四年，我为什么，为什么不好好读书，没找到和你一样的工作。
B 君某天看到了这样一个题，勾起了无穷的回忆。
输入(n, k) 和一棵(n) 个点的树，有边权，没有点权。两点(i, j) 之间的距离(D(i, j)) 定义为路径上的边权和。求
[
sum_1 leq i < j leq n leftlceil fracD(i,j)k
ight
ceil
]
换句话说，枚举无序的两个点，求出距离除以(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 fracxk
ceil = fracx + k - x modkk
]
所以我们需要求出分别有多少路径模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
",ans/k);
// fclose(stdin);
// fclose(stdout);
return 0;
test20181019b君的第三题(代码片段)
题意B君的第三题(urumqi)题目描述风雨如晦，鸡鸣不已。B君最近在研究自己的学长都在做什么工作，每个学长属于一个公司。B君会获得一些信息，比如x和y在相同公司，x和y在不同公司。如果当前信息和之前记住的所有信息都不矛... 查看详情
test20181016b君的第一题(代码片段)
题意分析考场爆零做法考虑位数少的一定更小，高位小的一定更少。然后计算一定位数下不同数字的个数，然后从高到低依次确定数位。特例：如果确定的高位的后缀出现了x，那么要把x调整到后缀去，这样一定更优。然而这样... 查看详情
noiac132b君的第三题(树形dp)(代码片段)
传送门本来想用点分治做，结果root又求不对算的时候还算错了我好菜啊结果szr大佬告诉我是树形dp我好菜啊！！我们有$lceilfracxkceil=fracx+(k-x)\%kk$于是可以把这个拆成两部分来求，最后加在一起再除个k距离和很好求，连接x和fa[x]... 查看详情
test20181020b君的第一题(代码片段)
题意分析二次剩余问题。x,y相当于二次方程[x^2-bx+c=0modp]的两根。摸意义下的二次方程仍然考虑判别式(Delta=b^2-4c)。它能开根的条件是(Delta=0)或(Delta^fracp-12=1)若能开根，则根为(Delta^fracp+14)然后就是普通的解一元二次方程了。代码#i... 查看详情
test20181017b君的第二题(代码片段)
题意分析考场50分旁边的L君告诉我，求的就是非升子序列的个数，于是写了个树状数组。但是(mod2333>0)还需要组合数中没有2333的倍数，所以实际上只得了(a_ileq2333)的部分分，还好。#include<cstdlib>#include<cstdio>#include<cma... 查看详情
第二章第三题(代码片段)
...列表中追加元素“seven”，并输出添加后的列表请在列表的第1个位置插入元素“Tony”，并输出添加后的列表请修改列表第2个位置的元素为“Kelly”，并输出修改后的列表请删除列表中的元素“eric”，并输出修改后的列表请删除... 查看详情
leetcode第三题(longestsubstringwithoutrepeatingcharacters)三部曲之三：两次优化(代码片段)
...LeetCode第三题(LongestSubstringWithoutRepeatingCharacters)三部曲》的第三篇，之前的两篇文章列出了思路并写出了Java代码，虽然在LeetCode网站提交通过，但是成绩并不理想，40多毫秒的速度，与诸多优秀的方案有不小差距，今天就来一起优... 查看详情
leetcode第三题(longestsubstringwithoutrepeatingcharacters)三部曲之二：编码实现(代码片段)
...LeetCode第三题(LongestSubstringWithoutRepeatingCharacters)三部曲》的第二篇，前一篇文章已经列出了完整的解题思路，今天来将此思路转化为具体的Java代码；关键变量编码之前先确定几个关键变量：当前窗口中的元素都是不重复的，适合... 查看详情
b君的第九题(代码片段)
B君的第九题对于一个排列(a_1,a_2,dots,a_n)，如果对于一个i满足(a_i-1<a_i>a_i+1)则称i是一个极大值。我们认为(a_0=a_n+1=0)。考虑(1,2,dots,n)的所有排列，问有多少个排列恰好有m个极大值。输出答案对p取模的结果。(1lenle10^9,1lemle10,2lep... 查看详情
c_cpp第三题(代码片段)
hive面试题系列第三题-用户留存问题(代码片段)
...：（以基准日当天活跃的用户中，基准日之后的第1天还活跃的用户数）/基准日当天总活跃用户数；第3日留存率：（以基准日当天活跃的用户中，基准日之后的第3天还活跃的用户数）/基准日当... 查看详情
i-nicetomeetyou(代码片段)
传送门和10-17 B君的第三题 类似，应该算是简化版，给出了固定的点。f[s]表示只考虑连端都在s集合中的边，s中的固定点（1或者2）能到达整个集合的方案数。预处理c[s]表示s集合中的总边数，转移就用所有方案减去s集合... 查看详情
leecode第三题（无重复字符的最长子串）(代码片段)
classSolutionpublic:intlengthOfLongestSubstring(strings)intlen=s.size();if(len==0||len==1)//边界returnlen;vector<int>is_here;for(inti=0;i<256;i++)//ASCII字符一共256个，建立一个辅助空间存储每个字符最后出现的位置is_here. 查看详情
ccf系列题解--2017年12月第三题crontab(代码片段)
样例输入320171117003220171122235207**1,3-5get_up3023**Sat,Sungo_to_bed1512,18***have_dinner样例输出201711170700get_up201711171215have_dinner201711171815have_dinner201711181215have_dinner201711181815have_dinne 查看详情
hive面试题系列第三题-用户留存问题(代码片段)
视频讲解地址：https://www.bilibili.com/video/BV1Rd4y1T7iU/?spm_id_from=333.788&vd_source=aa4fb0436f6d978af872cafb81a01178Hive面试题系列第三题-用户留存问题题目：求用户1日、3日、7日留存率概念问题：第N日活跃用户留存率&# 查看详情
欧拉项目第三题之最大质数因子(代码片段)
13195的质数因子有5,7,13和29.600851475143的最大质数因子是多少？这里可以肯定的是：1.数字很大，绝对不能暴力。2.如果这是一到OJ题，那么我们的目的就是尽量缩小这个数，减少计算量。我们都知道，任何一个合数都是可以由他的... 查看详情
数论专题第三题：c-aladdinandtheflyingcarpet(代码片段)
可能还是太菜了，最近每写一道题都会显得十分吃力，不过令人欣慰的是还可以从中学到不少的东西。题目的大概意思：给出面积啊a,还有最短的边b,求出能够组成矩形一共有多少个组合。samoleinput:102122sampleoutput:1 &nb... 查看详情
2021.9.8华为笔试题第三题(代码片段)
复盘一下华为第三道笔试题，当时没时间了，马上就写完了，感觉每次在牛客做题都得调半天才能过华为笔试最后一题基本都是出这种，当前任务依赖其他任务，拓扑排序这种题，或者是什么工序题目描述... 查看详情