校园网站建设指导思想,个体工商户注册网站,html网站地图模板,如何制作橡皮泥 简单换根DP
一般是给定一棵不定根树#xff0c;求以每个节点为根的一些信息。可以通过二次扫描#xff1a;
第一次扫描#xff0c;任选一点为根#xff0c;在有根树上#xff0c;自底向上转移第二次扫描#xff0c;从上一次扫描的根开始#xff0c;自顶向下计算
P3478 [P…换根DP
一般是给定一棵不定根树求以每个节点为根的一些信息。可以通过二次扫描
第一次扫描任选一点为根在有根树上自底向上转移第二次扫描从上一次扫描的根开始自顶向下计算
P3478 [POI2008] STA-Station
题意
询问以哪个节点为根所有节点的深度和最大。深度为到根节点的距离。
解析
第一次扫描以节点1为根(任意一个节点都可以)求出深度和。
第二次扫描设第一次扫描时 v v v 是 u u u 的儿子。假设根节点由 u u u 变为 v v v v v v 子树内所有节点的深度-1不在 v v v 子树内的所有节点深度1。 f v f u − s i z e v n − s i z e v f_v f_u-size_vn-size_v fvfu−sizevn−sizev n n n 为所有节点数。
代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn 1e610;
const int INF 0x3f3f3f3f;
typedef pairint, int pii;struct edge{int to, nxt;
}e[maxn 1];
int head[maxn], siz[maxn], tot, dep[maxn];
void add(int a, int b){e[tot].nxt head[a];e[tot].to b;head[a] tot;
}
int n, m;
ll f[maxn];
void dfs(int u, int fa){siz[u] 1;dep[u] dep[fa] 1;for(int i head[u]; i; i e[i].nxt){int v e[i].to;if(v fa)continue;dfs(v, u);siz[u] siz[v];}
}
void dfs2(int u, int fa){for(int i head[u]; i; i e[i].nxt){int v e[i].to;if(v fa)continue;f[v] f[u] n - siz[v] * 2;dfs2(v, u);}
}
signed main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin n;for(int i 1; i n; i){int u, v;cin u v;add(u, v); add(v, u);}dfs(1, 0);for(int i 1; i n; i)f[1] dep[i];dfs2(1, 0);ll maxx -1, res;for(int i 1; i n; i){if(maxx f[i]){res i;maxx f[i];}}cout res endl;return 0;
} P2986 [USACO10MAR] Great Cow Gathering G
题意
一棵树边有边权点有点权。询问以哪个点为根时 ∑ i 1 n d i s ( i , r o o t ) ⋅ a i \sum\limits_{i1}\limits^ndis(i, root) \cdot a_i i1∑ndis(i,root)⋅ai。 a i a_i ai 为点权 d i s ( i , r o o t ) dis(i,root) dis(i,root) 为节点 i i i 与根节点的距离。
解析
第一次扫描 以1节点为根 f u f_u fu 表示 u u u 子树内节点到 u u u 距离点权的乘积的和。设 v v v 为 u u u 的儿子则 f u ∑ ( f v s i z e v × e ( u , v ) ) f_u \sum(f_vsize_v\times e(u,v)) fu∑(fvsizev×e(u,v)) e ( u , v ) e(u,v) e(u,v) 为 ( u , v ) (u,v) (u,v) 边的长度。
第二次扫描 设第一次扫描时 v v v 是 u u u 的儿子。假设根节点由 u u u 变为 v v v v v v 子树内所有节点到根节点的距离减小 e ( u , v ) e(u,v) e(u,v)不在 v v v 子树内的所有节点到根节点的距离增加 e ( u , v ) e(u,v) e(u,v)。 f v f u ( n − 2 × s i z e v ) × e ( u , v ) f_v f_u(n-2\times size_v)\times e(u,v) fvfu(n−2×sizev)×e(u,v) n n n 为所有节点数。
代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn 1e610;
const ll INF 0x3f3f3f3f3f3f3f3f;
typedef pairint, int pii;#define int ll
struct edge{int to, nxt, w;
}e[maxn 1];
int head[maxn], siz[maxn], tot;
void add(int a, int b, int c){e[tot].nxt head[a];e[tot].to b;e[tot].w c;head[a] tot;
}
int n, m;
ll f[maxn], a[maxn], sum;
void dfs(int u, int fa){siz[u] a[u];for(int i head[u]; i; i e[i].nxt){int v e[i].to;if(v fa)continue;dfs(v, u);siz[u] siz[v];f[u] f[v] siz[v] * e[i].w;}
}
void dfs2(int u, int fa){for(int i head[u]; i; i e[i].nxt){int v e[i].to;if(v fa)continue;f[v] f[u] - siz[v] * e[i].w (sum - siz[v]) * e[i].w;dfs2(v, u);}
}
signed main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin n;for(int i 1; i n; i){cin a[i];sum a[i];}for(int i 1; i n; i){int u, v, w;cin u v w;add(u, v, w); add(v, u, w);}dfs(1, 0);dfs2(1, 0);ll res INF;for(int i 1; i n; i)res min(res, f[i]);cout res endl;return 0;
} 积蓄程度
题意
一棵树根节点可以流出无限水叶子节点可以吸收无限水每条边有流量限制。询问以哪个点为根节点时叶子节点吸收的水最多。
解析
第一次扫描
令 f u f_u fu 为以1为根节点时以 u u u 为根的子树中吸收的水量。
设 v v v 为 u u u 的儿子 { f u m i n ( f v , w ( u , v ) ) , d e g v 1 f u w ( u , v ) , d e g v ≠ 1 \begin{cases} f_u min(f_v, w(u, v)), deg_v 1\\ f_u w(u, v), deg_v \neq 1 \end{cases} {fumin(fv,w(u,v)),fuw(u,v),degv1degv1
第二次扫描
令 g u g_u gu 为以 u u u 为根节点时最大流量。
设第一次扫描时 v v v 是 u u u 的儿子。假设根节点由 u u u 变为 v v v g v g_v gv 包括两部分:
一部分是第一次扫描的 f v f_v fv一部分是流向 u u u 进而流向其他节点
对 u u u 而言从 u u u 到 v v v 的流量为 m i n ( f j , w ( i , j ) ) min(f_j, w(i,j)) min(fj,w(i,j))流向 v v v 之外的流量为 g u − m i n ( f j , w ( i , j ) ) g_u - min(f_j, w(i,j)) gu−min(fj,w(i,j))。所以 g v g_v gv 的第二部分为 m i n ( w ( u , v ) , g u − m i n ( f j , w ( i , j ) ) ) min(w(u,v), g_u - min(f_j, w(i,j))) min(w(u,v),gu−min(fj,w(i,j)))。也需要按照度是否为1讨论一下 { g v f v w ( u , v ) d e g u 1 g v f v m i n ( g u − w ( u , v ) , w ( u , v ) ) d e g u ≠ 1 , d e g v 1 g v f v m i n ( g u − m i n ( f v , w ( u , v ) ) , w ( u , v ) ) , d e g u ≠ 1 , d e g v ≠ 1 \begin{cases} g_v f_v w(u, v) deg_u 1\\ g_v f_v min(g_u-w(u,v), w(u, v)) deg_u \neq 1 ,deg_v 1\\ g_v f_v min(g_u-min(f_v, w(u,v)), w(u,v)), deg_u \neq 1 ,deg_v \neq 1 \end{cases} ⎩ ⎨ ⎧gvfvw(u,v)gvfvmin(gu−w(u,v),w(u,v))gvfvmin(gu−min(fv,w(u,v)),w(u,v)),degu1degu1,degv1degu1,degv1
代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn 2e510;
const int INF 0x3f3f3f3f;
typedef pairint, int pii;#define int ll
struct edge{int to, nxt, w;
}e[maxn 1];
int head[maxn], siz[maxn], tot;
void add(int a, int b, int c){e[tot].nxt head[a];e[tot].to b;e[tot].w c;head[a] tot;
}
int n, m;
ll f[maxn], g[maxn], deg[maxn];
void dfs(int u, int fa){f[u] 0;for(int i head[u]; i; i e[i].nxt){int v e[i].to;if(v fa)continue;dfs(v, u);if(deg[v] 1)f[u] e[i].w;elsef[u] min(e[i].w, f[v]);}
}
void dfs2(int u, int fa){for(int i head[u]; i; i e[i].nxt){int v e[i].to;if(v fa)continue;if(deg[u] 1)g[v] f[v] e[i].w;else if(deg[v] 1)g[v] f[v] min(g[u]-e[i].w, e[i].w);elseg[v] f[v] min(g[u]-min(f[v], e[i].w), e[i].w);dfs2(v, u);}
}
void solve(){cin n;memset(deg, 0, sizeof(deg));tot 0;memset(head, 0, sizeof(head));for(int i 1; i n; i){int a, b, c;cin a b c;add(a, b, c);add(b, a, c);deg[a]; deg[b];}dfs(1, 0);g[1] f[1];dfs2(1, 0);ll res 0;for(int i 1; i n; i)res max(res, g[i]);cout res endl;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int T;cin T;while(T--)solve();return 0;
}
