树形dp入门

树形dp

求树的重心

树上任意一点到其他所有点的距离的和

x为y的子树
$ ans[x] = ans[y] + (n-num[x]) -num[x] $

ac code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define lowbit(x) (x&(-x))
#define inc(i, l, r) for(int i=l; i<=r; i++)
#define dec(i, r, l) for(int i=r; i>=l; i--)
const int inf = 0x3f3f3f3f;
const int maxn = 100000+10;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int mod = 1e9+7;
int readint()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll readll(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n, m;
struct Node{
int v, w, next;
}node[maxn<<1];
int tot, head[maxn];
bool vis[maxn];
int sz[maxn];
int depth[maxn];
void init(){
tot = 0;
cls(head, -1);
cls(vis, 0);
}
void add_edge(int u, int v, int w){
node[tot].v=v;
node[tot].w=w;
node[tot].next = head[u];
head[u] = tot++;
}
void dfs(int u, int fa, int dep){
vis[u] = true;
depth[u] = dep;
sz[u] = 1;
for(int i=head[u];~i; i=node[i].next){
int v=node[i].v;
if(vis[v]||v==fa) continue;
dfs(v, u, dep+1);
sz[u] += sz[v];
}
}
ll ans[maxn];
void dfs1(int u, int fa){
ans[u] = ans[fa]+n-sz[u]-sz[u];
for(int i=head[u]; ~i; i=node[i].next){
int v = node[i].v;
if(v == fa) continue;
dfs1(v, u);
}
}
void solve(){
for(int i=head[1]; ~i; i=node[i].next){
int v=node[i].v;
dfs1(v, 1);
}
}
int main()
{
while(~scanf("%d", &n)){
int u, v;
init();
inc(i, 1, n-1){
u=readint(), v=readint();
add_edge(u, v, 1), add_edge(v, u, 1);
}
dfs(1, -1, 0);
inc(i, 1, n) ans[1] += depth[i];
solve();
inc(i, 1, n) printf("%lld\n", ans[i]);
}
return 0;
}

网络赛的题目

一直WA

树上经过任意一个点的最长链

这个题目不是整棵树的最长链,而这条最长链必须要经过我们要求的节点

未解决的问题

文章目录
  1. 1. 求树的重心
  2. 2. 树上任意一点到其他所有点的距离的和
    1. 2.1. ac code
  3. 3. 网络赛的题目
  4. 4. 树上经过任意一个点的最长链
  5. 5. 未解决的问题
{{ live2d() }}