HDU 6053 TrickGCD 容斥 DFS 分段快速查询

http://acm.hdu.edu.cn/showproblem.php?pid=6053

TrickGCD

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Problem Description

You are given an array $A$ , and Zhu wants to know there are how many different array $B$ satisfy the following conditions?
* $1\leq B_{i} \leq A_{i}$
* For each pair( l , r ) ($1 \leq l \leq r \leq n$) , $gcd( b_{l} , b_{l+1} ... b_{r} )\ge 2$

Input

The first line is an integer T($1 \leq T \leq 10$) describe the number of test cases.
Each test case begins with an integer number n describe the size of array $A$.
Then a line contains $n$ numbers describe each element of $A$
You can assume that $1 \leq n , A_{i} \leq 10^5$

Output

For the $k$th test case , first output "Case #k: " , then output an integer as answer in a single line . because the answer may be large , so you are only need to output answer $mod$ $10^9+7$

Sample Input

1
4
4 4 4 4

Sample Output

Case #1: 17

Source

题意

给定一个$A_i$数组,构造一个$B_i$数组,满足 $1\leq B_{i} \leq A_{i}$,且$B_i$数组的最大公约数不为1

思路

先将$A_i$排序,使用dfs枚举是否使用每一个质因子,容斥计算$B_i$数组的每一个数是dfs枚举的数的积的倍数。对于每次询问枚举出的数,不能暴力计算方案数,计算每个结果出现的次数即可。

详细题解

先将A数组排序,方便后续处理
枚举gcd是[一些质数的积的倍数],假设这个积为now, 那么要求B数组中每个数都是now的倍数,才能满足B数组的gcd是now的倍数。

对于一个给定的now值,如何求B数组中每个数都是now的倍数的方案呢?
由于1<=B[i]<=A[i],要求B[i]是now的倍数,那么B[i]就有A[i]/now向下取整种可能性,每个B[i]相互独立,将A[i]/now求积即可,但是这样做很容易就超时了。
令t = A[i]/now。发现t的范围是A[1]/now到A[n]/now,如果now比较大的话,这个范围会非常的小。考虑枚举这个t值,求有多少个A[i]满足A[i]/now=t就好了。
由于A数组已经排好序了,对于一个t,那么最小的一个数x使得x/now = t的就是x = now * t,最大的一个y是y=(t+1)*now-1,
在A数组中查找第一个大于等于x的数,查找第一个大于y的数,这两个位置相减,就是满足A[i]/now=t的i的个数len。
最后用快速幂powMod(t,len)来表示A[i]/now = t这len个数除以now向下取整之后的积,再将不同的t得到的乘起来,得到[B数组中每个数都是now的倍数的方案数]。

枚举这个now值的时候会发现,如果枚举了now1和now2,就会造成now1*now2这个值的方案数会算重,需要用容斥减去。
枚举是否选每一个质数,如果选了奇数个质数,那么答案+上这奇数个数造成的方案数,否则ans-去这偶数个数造成的方案数。
如何进行枚举?
用dfs枚举是否选择每一个质数,用k记录已经选的质数的积,用一个变量f,值为1或-1来记录已经选取的质数的个数的奇偶性, now代表正在枚举是否选这个数的下标。
首先,如果now超过了质数的个数,可以return了。
先要明确以点,如果k已经大于了A[1],那么就没用方案了,A[1]怎么可能是一个比他自己还大的数的倍数嘛……
所以假设选取质数p[now],如果p[now] * k > A[1]了,也可以return了
接下来就是算 p[now] *k造成的方案数了,ans += f*造成的方案数。
最后继续进行dfs,枚举是否选这个数,如果选了这个数,k变为k*p[now],f=-f。

 

 

HDU 6052 To my boyfriend 询问分块 容斥 单调栈

http://acm.hdu.edu.cn/showproblem.php?pid=6052

To my boyfriend

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)



Problem Description

Dear Liao
I never forget the moment I met with you. You carefully asked me: "I have a very difficult problem. Can you teach me?". I replied with a smile, "of course". You replied:"Given a matrix, I randomly choose a sub-matrix, what is the expectation of the number of **different numbers** it contains?"
Sincerely yours,
Guo

Input

The first line of input contains an integer T(T≤8) indicating the number of test cases.
Each case contains two integers, n and m (1≤n, m≤100), the number of rows and the number of columns in the grid, respectively.
The next n lines each contain m integers. In particular, the j-th integer in the i-th of these rows contains g_i,j (0≤ g_i,j < n*m).

Output

Each case outputs a number that holds 9 decimal places.

Sample Input

1
2 3
1 2 1
2 1 2

Sample Output

1.666666667

Hint

6(size = 1) + 14(size = 2) + 4(size = 3) + 4(size = 4) + 2(size = 6) = 30 / 18 = 6(size = 1) + 7(size = 2) + 2(size = 3) + 2(size = 4) + 1(size = 6)

Source

题意

给定一个$n*m$的矩阵,矩阵内每个点有个颜色。现任选一个子矩阵,问这个子矩阵包含的不同颜色个数的期望。

思路

单独求每种颜色对答案的贡献,对于一种颜色来说,如果点的个数超过了7个,直接使用单调栈来维护不含这个颜色的子矩阵的个数,否则使用容斥来算。对于单调栈维护来说,枚举每一行,算出这一行的每一个点往上多高不会包含这种颜色,分别用单调栈维护以每个点作为右下角的方案即可。容斥的计算总方案数-至少包含一个点的+至少包含两个点的-……

 

 
 

HDU 6050 Funny Function 矩阵快速幂 矩阵变化

http://acm.hdu.edu.cn/showproblem.php?pid=6050

Funny Function

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Problem Description

Function $F_{x,y}$satisfies:

For given integers N and M,calculate $F_{m,1}$ modulo 1e9+7.
Input
There is one integer T in the first line.
The next T lines,each line includes two integers N and M .
1<=T<=10000,1<=N,M<2^63.
Output
For each given N and M,print the answer in a single line.

Sample Input

2
2 2
3 3

Sample Output

2
33

Source

题意

给定上图公式和$n,m$,求$F_{m,1}$

思路

可以发现,$F_{i,j} = F_{i,j-1}+2*F_{i,j-2}$,对于每行,维护出$F_j, F_{j-1},Sum_j,F_1$,用矩阵快速幂计算即可。转移到下一行,
$$F_j = Sum_{n+1} - F_1$$
$$F_{j-1} = Sum_{n+1} - F_n$$
$$Sum_j = 2* Sum_{n+1} -  F_1 - F_n$$
$$F_1 = Sum_{n+1} - F_n$$
上述变化是线性的,前面乘以一个矩阵即可表示。最后将所得的矩阵快速幂$m-1$次后,乘上维护的信息,就是最后的答案。

 

 

HDU 6047 Maximum Sequence 贪心 优先队列

http://acm.hdu.edu.cn/showproblem.php?pid=6047

Maximum Sequence

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Problem Description

Steph is extremely obsessed with “sequence problems” that are usually seen on magazines: Given the sequence 11, 23, 30, 35, what is the next number? Steph always finds them too easy for such a genius like himself until one day Klay comes up with a problem and ask him about it.
Given two integer sequences {ai} and {bi} with the same length n, you are to find the next n numbers of {ai}: $a_{n+1}…a_{2n}$. Just like always, there are some restrictions on $a_{n+1}…a_{2n}$: for each number $a_i$, you must choose a number $b_k$ from {bi}, and it must satisfy $a_i$≤max{$a_j$-j│$b_k$≤j<i}, and any $b_k$ can’t be chosen more than once. Apparently, there are a great many possibilities, so you are required to find max{$\sum_{n+1}^{2n}a_i$} modulo $10^9$+7 .
Now Steph finds it too hard to solve the problem, please help him.

Input

The input contains no more than 20 test cases.
For each test case, the first line consists of one integer n. The next line consists of n integers representing {ai}. And the third line consists of n integers representing {bi}.
1≤n≤250000, n≤a_i≤1500000, 1≤b_i≤n.

Output

For each test case, print the answer on one line: max{$\sum_{n+1}^{2n}a_i$} modulo $10^9$+7。

 Sample Input

Sample Output

Hint

For the first sample: 1. Choose 2 from {bi}, then a_2…a_4 are available for a_5, and you can let a_5=a_2-2=9; 2. Choose 1 from {bi}, then a_1…a_5 are available for a_6, and you can let a_6=a_2-2=9;

Source

题意

给定两个长度为$n$数组$a_i,b_i$,现在要把$a_i$补充到长度为$2n$,从左到右补充,对于每一个$a_i$,需要选取一个未使用的$b_k$,$a_i$ 为$a$数组在$b_k~i-1$区间内的最小值。求$\sum_{n+1}^{2n}a_i$的最大值。

思路

对于每次取数,尽量取大即可,即使用当前能使用的最小的$b_k$。那么对$b_i$排序,将$a_i-i$放入优先队列,每次将堆顶的不合法元素弹掉,再取值记录答案,再将取出的值减去下标后压入优先队列。

 

 

HDU 6044 Limited Permutation DFS计算方案数

http://acm.hdu.edu.cn/showproblem.php?pid=6044

Limited Permutation

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description

As to a permutation $p_1, p_2, \cdots, p_n$ from $1$ to $n$, it is uncomplicated for each $1 \leq i \leq n$ to calculate $(l_i, r_i)$ meeting the condition that $\min(p_L, p_{L + 1}, \cdots, p_R) = p_i$ if and only if $l_i \leq L \leq i \leq R \leq r_i$ for each $1 \leq L \leq R \leq n$.
Given the positive integers $n$, $(l_i, r_i)$ $(1 \leq i \leq n)$, you are asked to calculate the number of possible permutations $p_1, p_2, \cdots, p_n$ from $1$ to $n$, meeting the above condition.
The answer may be very large, so you only need to give the value of answer modulo $10^9 + 7$.

Input

The input contains multiple test cases.
For each test case:
The first line contains one positive integer $n$, satisfying $1 \leq n \leq 10^6$.
The second line contains $n$ positive integers $l_1, l_2, \cdots, l_n$, satisfying $1 \leq l_i \leq i$ for each $1 \leq i \leq n$.
The third line contains $n$ positive integers $r_1, r_2, \cdots, r_n$, satisfying $i \leq r_i \leq n$ for each $1 \leq i \leq n$.
It's guaranteed that the sum of $n$ in all test cases is not larger than $3 \cdot 10^6$.
Warm Tips for C/C++: input data is so large (about 38 MiB) that we recommend to use fread() for buffering friendly.

Output

For each test case, output "Case #$x$: $y$" in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y$ denotes the answer of corresponding case.

Sample Input

3
1 1 3
1 3 3
5
1 2 2 4 5
5 2 5 5 5

Sample Output

Case #1: 2
Case #2: 3

Source

题意

求一个长度为$n$的排列的方案数,给出n个限制条件$l_i,r_i$,表示当且经当$l_i \leq L \leq i \leq R \leq r_i$的时候,$\min(p_L, p_{L + 1}, \cdots, p_R) = p_i$ ,否则一定不是。

思路

根据题述条件推得,对于每一对$l_i,r_i$来说,如果其左边存在,那么左边第一个数一定小于$p_i$,同理,右边的第一个数一定小于$p_i$。那么,对于所有的$l_i,r_i$来说,只存在包含和相离两种关系,绝对不能包含相交和重叠的关系,否则无解。对于一对$l_i,r_i$来说,该区间内的最小值一定在i位置,把这个最小值的位置确定下来后,还有$r_i-l_i$个数的位置不确定,现在,左区间的长度为$i-l_i$,那么选取$其中i-l_i$个数放到左区间,其余的放到右区间,计算组合数,递归出来左右区间即可。

 

HDU 6036 I Curse Myself 仙人掌的最小生成树

http://acm.hdu.edu.cn/showproblem.php?pid=6041

I Curse Myself

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description

There is a connected undirected graph with weights on its edges. It is guaranteed that each edge appears in at most one simple cycle.
Assuming that the weight of a weighted spanning tree is the sum of weights on its edges, define $V(k)$ as the weight of the $k$-th smallest weighted spanning tree of this graph, however, $V(k)$ would be defined as zero if there did not exist $k$ different weighted spanning trees.
Please calculate $\displaystyle\left(\sum_{k=1}^{K}{k \cdot V(k)}\right) \bmod 2^{32}$.

Input

The input contains multiple test cases.
For each test case, the first line contains two positive integers $n, m$ $(2 \leq n \leq 1000, n-1 \leq m \leq 2n-3)$, the number of nodes and the number of edges of this graph.
Each of the next $m$ lines contains three positive integers $x, y, z$ $(1 \leq x, y \leq n, 1 \leq z \leq 10^6)$, meaning an edge weighted $z$ between node $x$ and node $y$. There does not exist multi-edge or self-loop in this graph.
The last line contains a positive integer $K$ $(1 \leq K \leq 10^5)$.

Output

For each test case, output "Case #$x$: $y$" in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y$ denotes the answer of corresponding case.
Sample Input

Sample Output

Source

 

题意

给一个$n$个点的无向图,保证一条边最多属于一个环,求前$k$小生成树的权重*排名的和。

思路

可以发现这是一颗仙人掌图,对于每一个环来说,最小生成树上会不包含上面的一条边。换句话说,边权的总和,减去每个环上的一条边,就是一颗生成树。那么就是每个环贡献一条边,求这些边和前$k$大值。考虑这$m$个环上的边,构成了$m$个数组,我们只需要对数组两两合并,维护前$k$大值即可。合并的时候采用优先队列,将长度短的数组的每一个数$b_i + a_0$放入优先队列,弹出的时候,记录答案,修改$a$元素为较大的一个后继续放入优先队列(这里$a$数组已经排序)。

 

 

 
 

HDU6040 Hints of sd0061 分治排序

http://acm.hdu.edu.cn/showproblem.php?pid=6040

Hints of sd0061

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description

sd0061, the legend of Beihang University ACM-ICPC Team, retired last year leaving a group of noobs. Noobs have no idea how to deal with $m$ coming contests. sd0061 has left a set of hints for them.
There are $n$ noobs in the team, the $i$-th of which has a rating $a_i$. sd0061 prepares one hint for each contest. The hint for the $j$-th contest is a number $b_j$, which means that the noob with the $(b_j + 1)$-th lowest rating is ordained by sd0061 for the $j$-th contest.
The coach asks constroy to make a list of contestants. constroy looks into these hints and finds out: $b_i + b_j \leq b_k$ is satisfied if $b_i \neq b_j,$ $b_i < b_k$ and $b_j < b_k$.
Now, you are in charge of making the list for constroy.

Input

There are multiple test cases (about $10$).
For each test case:
The first line contains five integers $n, m, A, B, C$. $(1 \leq n \leq 10^7, 1 \leq m \leq 100)$
The second line contains $m$ integers, the $i$-th of which is the number $b_i$ of the $i$-th hint. $(0 \leq b_i < n)$
The $n$ noobs' ratings are obtained by calling following function $n$ times, the $i$-th result of which is $a_i$.

Output

For each test case, output "Case #$x$: $y_1$ $y_2$ $\cdots$ $y_m$" in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y_i$ $(1 \leq i \leq m)$ denotes the rating of noob for the $i$-th contest of corresponding case.

Sample Input

Sample Output

Source

题意

给一个随机程序,生成一个长度为n的数组$a_i$,再给m次寻问$b_i$,询问数组$a_i$排序后,排名为$b_i+1$的数是多少。

思路

将询问的$b_i$数组排序,对$a_i$数组进行分治,类似于快排,选取参考点,交换数据后,在$b_i$数组中二分查找mid的范围,那么此时$b_i=mid$的询问都做出来了,此时$a_i$$b_i$数组都分成了左右两部分,直接递归处理这两部分即可。

 

 

HDU 6039 Gear Up 并查集 dfs序 线段树

http://acm.hdu.edu.cn/showproblem.php?pid=6039

Gear Up

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description

constroy has some gears, each with a radius. Two gears are considered adjacent if they meet one of the following conditions:
1. They share a common edge (i.e. they have equal linear velocity).
2. They share a common shaft (i.e. they have equal angular velocity).
It is guaranteed that no pair of gears meets both of the above conditions.
A series of continuous adjacent gears constitutes a gear path. There is at most one gear path between each two gears.
Now constroy assigns an angular velocity to one of these gears and then asks you to determine the largest angular velocity among them.
sd0061 thinks this problem is too easy, so he replaces some gears and then asks you the question again.

Input

There are multiple test cases (about $30$).
For each test case:
The first line contains three integers $n, m, q$, the number of gears, the number of adjacent pairs and the number of operations. $(0 \leq m < n \leq 10^5, 0 \leq q \leq 10^5)$
The second line contains $n$ integers, of which the $i$-th integer represents $r_i$, the radius of the $i$-th gear. $(r_i \in \{2^\lambda \mid 0 \leq \lambda \leq 30\})$
Each of the next $m$ lines contains three integers $a, x, y$, the $x$-th gear and the $y$-th gear are adjacent in the $a$-th condition. $(a \in \{1, 2\}, 1 \leq x, y \leq n, x \neq y)$
Each of the next $q$ line contains three integers $a, x, y$, an operation ruled in the following: $(a \in \{1, 2\}, 1 \leq x \leq n, y \in \{2^\lambda \mid 0 \leq \lambda \leq 30\})$
$a = 1$ means to replace the $x$-th gear with another one of radius $y$.
$a = 2$ means to assign angular velocity $y$ to the $x$-th gear and then determine the maximum angular velocity.

Output

For each test case, firstly output "Case #$x$:" in one line (without quotes), where $x$ indicates the case number starting from $1$, and then for each operation of $a = 2$, output in one line a real number, the natural logarithm of the maximum angular velocity, with the precision of $3$ digits.

Sample Input

Sample Output

Source

题意

给n个齿轮,每个齿轮都有各自的半径,再给m对齿轮关系,有共边和共轴两种。有q次操作,每次操作会修改某个齿轮的半径,或者是给以某个齿轮一个角速度,问和他连通的齿轮组内角速度最大齿轮的角速度。保证输入的半径或者角速度都是2的整数次方幂。输出的答案取自然对数。保证齿轮关系构成的图没有环。

思路

使用并查集维护共轴的齿轮关系。在每个齿轮连通块中选取一个参考齿轮,将所有的速度和半径对2取对数后,角速度之间差距就从倍数变成了差值,方便计算。从参考齿轮开始,进行dfs,并维护dfs序,优先dfs和这个齿轮共边的齿轮,并计算每个齿轮对于参考齿轮的角速度差,和这个齿轮u共边的齿轮v,他们的角速度都是都是比u的相对角速度快r[u]-r[v],其中r为半径,并且记每个v齿轮在树上的父亲为u。记录下这个dfs序的起止位置为edgeL[u],edgeR[u]。再dfs和这个齿轮共轴的齿轮,这些齿轮的角速度和u相同,并且记这些齿轮的在树上的父亲为不存在。记录这段dfs序列的起止位置为shaftL[u]和shaftR[u]。

询问的时候,先计算出参考齿轮的角速度,再求整个连通块内的最大值即可,区间应该为edgeL[u]~shaftR[u]。

修改分为两种情况。如果这个齿轮在树上没有父亲,那么修改他的半径,只会影响和他共边的齿轮以及共边齿轮连接的齿轮,区间为edgeL[u]+1~edgeR[u]。如果有父亲,则会影响他自己的角速度以及和他共轴齿轮及他们连接的齿轮,区间为edgeL[u]~edgeL[u],shaftL[u]~shaftR[u]。每次修改,对上述区间进行区间累加,维护最大值即可。

 

HDU 6038 Function 循环节 方案数

http://acm.hdu.edu.cn/showproblem.php?pid=6038

Function

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description

You are given a permutation $a$ from $0$ to $n - 1$ and a permutation $b$ from $0$ to $m - 1$.
Define that the domain of function $f$ is the set of integers from $0$ to $n - 1$, and the range of it is the set of integers from $0$ to $m - 1$.
Please calculate the quantity of different functions $f$ satisfying that $\displaystyle f(i) = b_{f(a_i)}$ for each $i$ from $0$ to $n - 1$.
Two functions are different if and only if there exists at least one integer from $0$ to $n - 1$ mapped into different integers in these two functions.
The answer may be too large, so please output it in modulo $10^9 + 7$.

Input

The input contains multiple test cases.
For each case:
The first line contains two numbers $n,$ $m$. $(1 \leq n \leq 100000, 1 \leq m \leq 100000)$
The second line contains $n$ numbers, ranged from $0$ to $n - 1$, the $i$-th number of which represents $a_{i - 1}$.
The third line contains $m$ numbers, ranged from $0$ to $m - 1$, the $i$-th number of which represents $b_{i - 1}$.
It is guaranteed that $\sum{n} \leq 10^6,$ $\sum{m} \leq 10^6$.

Output

For each test case, output "Case #$x$: $y$" in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y$ denotes the answer of corresponding case.

Sample Input

3 2
1 0 2
0 1
3 4
2 0 1
0 2 3 1

Sample Output

Case #1: 4
Case #2: 4

Source

 

题意

给一个长度为$n$的排列$a_i$,再给一个长度为$m$的排列$b_i$,问有多少组映射$f(i)$,满足 $ f(i) = b_{f(a_i)}$

思路

$f(i) = b_{f(a_i)} = b_{b_{f(a_{a_i})}} = \underbrace{b_{\cdots b_{f(i)}}}_{l\text{ times }b}$

由于$a_i, b_i$都是排列,所以上述的等式一定成立,(注意倒数第二个表达式a的下标),假设a的一个循环节的长度一定要是l,那么对应一定b一个有个循环节,长度为l的一个约数。可以将a的这个循环节看成一个换,将b的一个循环节布在这个环上,有多少种本质不同的情况,其实就是b的这个循环节大小。对于a的每一个循环节,可以和b的任意一个满足长度要求的循环节任意组合。所以,枚举a的每一个循环节,找到所有满足要求的b循环节,计算方案累加即可。

 

HDU6035 Colorful Tree DFS + 统计对答案的贡献

http://acm.hdu.edu.cn/showproblem.php?pid=6035

Colorful Tree

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description

There is a tree with $n$ nodes, each of which has a type of color represented by an integer, where the color of node $i$ is $c_i$.
The path between each two different nodes is unique, of which we define the value as the number of different colors appearing in it.
Calculate the sum of values of all paths on the tree that has $\frac{n(n-1)}{2}$ paths in total.

Input

The input contains multiple test cases.
For each test case, the first line contains one positive integers $n$, indicating the number of node. $(2 \leq n \leq 200000)$
Next line contains $n$ integers where the $i$-th integer represents $c_i$, the color of node $i$. $(1 \leq c_i \leq n)$
Each of the next $n - 1$ lines contains two positive integers $x, y$ $(1 \leq x, y \leq n, x \neq y)$, meaning an edge between node $x$ and node $y$.
It is guaranteed that these edges form a tree.

Output

For each test case, output "Case #$x$: $y$" in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y$ denotes the answer of corresponding case.

Sample Input

Sample Output

Source

 

题意

给一个$n$个点的树,每个点有一种颜色。一条路径的权重被定义为这条路径上不同颜色的个数。求所有路径权重的总和。

思路

可以单独考虑每种颜色对答案的贡献,假设我们现在关注的颜色为$c_i$,求有多少条路径上含有这种颜色,最后求和即可。但是这个东西还是不好求,可以考虑在树上把这些点删掉,剩下的路径就是不含关注颜色点的路径,数目为$\sum各个连通块大小s_i*(s_i-1)/2$。最后总路径条数减去这个和值即可。现在问题就转化到了就每个连通块的大小。首先dfs求出每个子树的大小,再次dfs,假设当前点为u,颜色为c[u],对u的一个子树v进行搜索的时候,如果发现v的某个子树的颜色和c[u]相同,且这个子树和u的路径上没有再出现颜色c[u],则sz[v]减去这个子树的大小。最后sz[v]的大小就是从u点向v点走,一个不含c[u]颜色的连通块的大小。当然这只是思路,在实际dfs的时候,用一个栈st[c[u]]来记录c[u]颜色上一次出现在什么位置,回溯的时候需要将栈pop。当在搜到颜色和u点相同颜色的点的时候,直接将搜到的子树的大小记录到u节点上即可。最后还要注意,需要给树加一个虚根,并且每种颜色第一次出现都是在这个虚根上,方便计算答案。

PS:栈的容器类型需要换成vector,开$10^5$个栈会直接MLE的