NC51180 Accumulation Degree

题目地址:

https://ac.nowcoder.com/acm/problem/51180

基本思路:

通过看Alan巨巨的题解我学会了换根dp(orz Alan)；
我们先思考换根dp能解决一个什么样的问题,换根dp重点在换根,所以当一道题要我们统计将每个节点作为根的子树状态时我们一般要考虑换根dp;
我们看这道题:
这道题我们可以先通过基本的树形dp以1为根跑一边dfs,求出这种情况下以每个点为根的子树的流量最大值,这时我们有转移方程：
如果v为叶子节点 $图片说明$
如果v不是叶子节点 $图片说明$
然后我们换根;
我们将u为根变为以v为根,这个时候我们来考虑f[v]流量的两部分贡献,一部分是之前以1为根时它自己子树的最大流量即flow[v],还有一部分是父节点即u为子树的贡献，我们看这部分贡献如何求，首先： $图片说明$ (to代表u连着的所有节点v包含在其中),那么这个时候从u往v流的流量应该是这个值即f[u]去掉其中以v为根的这条子树的流量贡献即 $图片说明$ ,然后(u,v)这条边流量还有流量限制,所以综上,这个第二部分贡献为 $图片说明$
那么两部分贡献相加： $图片说明$
按照这个转移方程我们再一次dfs就能求出以所有节点为根的答案;
ps.由于是多组输入,记得初始化;

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define ll long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f

const int maxn = 2e5 + 10;
struct Edge{
    int to,next,cap;
}edge[maxn*2];
int n;
int cnt = 0,head[maxn];
int flow[maxn],du[maxn],f[maxn];
void add_edge(int u,int v,int cap) {
  edge[++cnt].next = head[u];
  edge[cnt].to = v;
  edge[cnt].cap = cap;
  head[u] = cnt;
}
void dfs1(int u,int p) {
  for (int i = head[u]; i != -1; i = edge[i].next) {
    int to = edge[i].to;
    if (to == p) continue;
    dfs1(to, u);
    if (du[to] == 1) flow[u] += edge[i].cap;
    else flow[u] += min(flow[to], edge[i].cap);
  }
}
void dfs2(int u,int p) {
  for (int i = head[u]; i != -1; i = edge[i].next) {
    int to = edge[i].to;
    if (to == p) continue;
    if (du[u] == 1) f[to] = flow[to] + edge[i].cap;
    else f[to] = flow[to] + min(f[u] - min(flow[to], edge[i].cap), edge[i].cap);
    dfs2(to, u);
  }
}
signed main() {
  IO;
  int t;
  cin >> t;
  while (t-->0) {
    cnt = 0;
    mset(head, -1);
    cin >> n;
    mset(du,0);
    mset(flow,0);
    mset(f,0);
    rep(i, 1, n - 1) {
      int u,v,w;
      cin >> u >> v >> w;
      add_edge(u, v, w);
      add_edge(v, u, w);
      du[u]++, du[v]++;
    }
    dfs1(1, 0);
    f[1] = flow[1];
    dfs2(1, 0);
    int ans = 0;
    rep(i, 1, n) ans = max(ans, f[i]);
    cout << ans << '\n';
  }
  return 0;
}

NC201400 树学

题目地址：

https://ac.nowcoder.com/acm/problem/201400

基本思路:

这题我们可以用刚学的换根dp来做,也可以再学习一下树的重心;
我们来看下百度百科里树的重心的性质：

树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个重心，他们的距离和一样。
把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。
一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。
一棵树最多有两个重心，且相邻。

那么根据题意,我们不难发现,这个性质1中描述树中所有点到某个点的距离和的刚好就是题目中的这个W,所以我们找到重心在求出这个W就行了;

那么树的重心怎么求,我们一般根据它的定义来求：
树的重心: 找到一个点,其所有的子树中最大的子树节点数最少.
那么这部分我们用树形dp，就有了以下的套路代码：

void dfs1(int u,int p) {
  sz[u] = 1;
  for (int i = head[u]; i != -1; i = edge[i].next) {
    int to = edge[i].to;
    if (to == p) continue;
    dfs1(to, u);
    sz[u] += sz[to];//更新u为节点的子树的节点数;
    f[u] = max(f[u], sz[to]);//子树最大的节点数;
  }
  f[u] = max(f[u], n - sz[u]);//n-sz[u]就是把它父节点作为根的子树的节点数;
  if (f[u] < mi) {//直接取子树中最大的子树节点数最少的节点为重心;
    mi = f[u];
    res = u;
  }
}

我们找到重心再以重心为根算出dep,就能加出答案。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f

const int maxn = 1e6 + 10;
struct Edge{
    int to,next;
}edge[maxn*2];
int n;
int cnt = 0,head[maxn];
void add_edge(int u,int v) {
  edge[++cnt].next = head[u];
  edge[cnt].to = v;
  head[u] = cnt;
}
int res = 0,mi = INF,sz[maxn],f[maxn];
void dfs1(int u,int p) {
  sz[u] = 1;
  for (int i = head[u]; i != -1; i = edge[i].next) {
    int to = edge[i].to;
    if (to == p) continue;
    dfs1(to, u);
    sz[u] += sz[to];//更新u为节点的子树的节点数;
    f[u] = max(f[u], sz[to]);//子树最大的节点数;
  }
  f[u] = max(f[u], n - sz[u]);//n-sz[u]就是把它父节点作为根的子树的节点数;
  if (f[u] < mi) {//直接取子树中最大的子树节点数最少的节点为重心;
    mi = f[u];
    res = u;
  }
}
int dep[maxn];
void dfs2(int u,int p){
  if(p == 0) dep[u] = 0;
  else dep[u] = dep[p] + 1;
  for(int i = head[u] ; i != -1 ; i = edge[i].next){
    int to = edge[i].to;
    if(to == p) continue;
    dfs2(to,u);
  }
}
signed main() {
  IO;
  cin >> n;
  cnt = 0;
  mset(head,-1);
  rep(i,1,n-1) {
    int u, v;
    cin >> u >> v;
    add_edge(u, v);
    add_edge(v, u);
  }
  dfs1(1,0);
  dfs2(res,0);
  int ans = 0;
  rep(i,1,n) ans += dep[i];
  cout << ans << '\n';
  return 0;
}

NC51180 Accumulation Degree + NC201400 树学

NC51180 Accumulation Degree

题目地址:

基本思路:

参考代码：

NC201400 树学

题目地址：

基本思路:

参考代码：