C Codeforces 191C

给你一棵树，有 $k$ 对节点，问每条边有多少对节点的路径经过。

解

树上差分搞一搞。（从下往上）

D BZOJ 3124

求一棵树直径长度、有多少条边满足所有的直径都经过该边。

解

求直径好办。

第二问中，在直径上按顺序访问（我们假设是从左到右）每一个节点做一遍dfs，如果搜到某个节点到当前节点的距离等于当前节点到直径左端点的距离，那么该节点左边的所有边一定不满足题意。

如果搜到某个节点到当前节点的距离等于当前节点到直径右端点的距离，那么break;。

E Codeforces 734E

一棵树，每个节点有黑、白两色。

现在可以进行若干次操作，每次选定一个节点，可以将所有满足条件的节点涂成与该节点相同的颜色：选定的节点与该节点的路径上所有节点的颜色都与该节点相同。

问最少几步能将整棵树涂成同一种颜色。

解

初始时和每次操作后将颜色相同且相邻的节点缩成一点（需使用并查集），然后建一棵缩点后的新树，然后求出该树的直径，答案为 $(直径+1)/2$ 。

方法是不停地更改一个节点的颜色。

F Codeforces 379F

给你一棵树，初始时长这样

然后进行 $n$ 次操作，每次选定一个节点，在它下面增加两个子节点，并询问当前树的直径。

解

每增加一个节点就检查它到直径两个端点的距离是否大于当前直径长度，如果大于，更新当前直径的一个端点。

两节点的距离用lca解决。

G Codeforces 294E

有一棵树，现在你要删除一条边，然后增加一条边权与删除的边的边权相等的边，需保证树依然连通，并最小化两两节点的距离和。输出这个距离和。

$(2 ≤ n ≤ 5000)$

解

先枚举每一条边作为删除的边，然后计算答案。

新建的边一定建在删边之后形成的两颗子树的重心之间。

然后运用加法原理+乘法原理dp一下。（有点复杂）（注意别忘开long long）

Code

#include
    
     #define maxn 5003#define INF 100000000000000000llusing namespace std;struct edge{    int to,next,w;}e[maxn<<1];int head[maxn],cnte,dep[maxn];void add(int u,int v,int w){    e[++cnte].to=v;    e[cnte].w=w;    e[cnte].next=head[u];    head[u]=cnte;}int n,G,sz[maxn];long long sumw[maxn],answ[maxn],sumG;void solve(int u,int last){    sz[u]=1;    sumw[u]=0;    answ[u]=0;    for(int i=head[u];i;i=e[i].next){        int v=e[i].to;        if(v==last)continue;        solve(v,u);        answ[u]+=answ[v]+sumw[v]*sz[u]+sumw[u]*sz[v]+(long long)sz[u]*sz[v]*e[i].w;        sumw[u]+=sumw[v]+(long long)e[i].w*sz[v];        sz[u]+=sz[v];    }}void dfs(int u,int last,int totsz){    sumG=min(sumG,sumw[u]);    for(int i=head[u];i;i=e[i].next){        int v=e[i].to;        if(v==last)continue;        sumw[v]=sumw[u]+(long long)(totsz-sz[v]-sz[v])*e[i].w;        dfs(v,u,totsz);    }}int main(){    scanf("%d",&n);    for(int i=1;i