Tree chain problemTime Limit: 6000/3000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 565Accepted Submission(s): 137
Problem Description
Coco has a tree, whose vertices are conveniently labeled by 1,2,…,n.There are m chain on the tree, Each chain has a certain weight. Coco would like to pick out some chains any two of which do not share common vertices.Find out the maximum sum of the weight Coco can pick
Input
The input consists of several test cases. The first line of input gives the number of test cases T (T<=10).For each tests:First line two positive integers n, m.(1<=n,m<=100000)The following (n – 1) lines contain 2 integers ai bi denoting an edge between vertices ai and bi (1≤ai,bi≤n),Next m lines each three numbers u, v and val（1≤u，，v≤n，0<val<1000）, represent the two end points and the weight of a tree chain.
Output
For each tests:A single integer, the maximum number of paths.
Sample Input
17 31 21 32 42 53 63 72 3 44 5 36 7 3
Sample Output
6
Hint
Stack expansion program： #pragma comment(linker, "/STACK:1024000000,1024000000")
Author
FZUACM
Source
#pragma comment(linker, "/STACK:1024000000,1024000000")#include <iostream>#include <cstring>#include <cstdio>#include <vector>#include <algorithm>using namespace std;#define prt(k) cerr<<#k" = "<<k<<endltypedef unsigned long long ll;const int N = 233333;int n, m, head[N], mm;struct Edge{int v, next, w;} e[N << 1];void add(int u, int v, int w = 1){e[mm].v = v;e[mm].next = head[u];e[mm].w = w;head[u] = mm++;}int sz[N], dep[N];int f[N][22]; /// f[i][j] 表示 i 的第 2^j 个祖先int dfn[N]; ///dfs indexint cur;int id[N]; /// you dfs xu qiu chu bian haoint len[N];int fa[N], son[N], top[N], p[N], pos;/// fa 父节点 dep — 深度sz 孩子数 son 重儿子/// top[u] 它所在重链顶端节点 p[u]在数据结构中位置 rp p的反void dfs(int u, int pre = 1) /// 点从 1 开始标号{sz[u] = 1;dfn[u] = ++cur;id[cur] = u;for (int i=head[u]; ~i; i=e[i].next){int v = e[i].v;int w = e[i].w;if (v != pre){dep[v] = dep[u] + 1;len[v] = len[u] + w;fa[v] = f[v][0] = u;dfs(v, u);sz[u] += sz[v];if (son[u]==-1 || sz[son[u]] < sz[v])son[u] = v;}}}/// top[u] 它所在重链顶端节点 p[u]在数据结构中位置void getpos(int u, int v = 1){top[u] = v;p[u] = ++pos;if (~son[u]) getpos(son[u], v);for (int i=head[u]; ~i; i=e[i].next){int v= e[i].v;if (v-son[u] && v-fa[u])getpos(v, v);}}int maxh;void gao(){cur = 0;dep[0] = -1;len[1] = dep[1] = 0;memset(son, -1, sizeof son);dfs(1, 0);int j;for (j=1; (1<<j)<n; j++)for (int i=1; i<=n; i++)f[i][j] = f[f[i][j-1]][j-1];maxh = j – 1;getpos(1);}int swim(int x, int k){for (int i=0; i<=maxh; i++)if (k >> i & 1)x = f[x][i];return x;}int LCA(int x, int y){if (dep[x] > dep[y]) swap(x, y); ///dep[x] <= dep[y];y = swim(y, dep[y] – dep[x]);if (x == y) return y;for (int i=maxh; i>=0; i–){if (f[x][i] != f[y][i])x = f[x][i], y = f[y][i];}return f[x][0];}int lca[N];struct P{int u, v, w;P() {}P(int _u,int _v, int _w) {u=_u, v=_v, w=_w;}} chain[N]; /// chains;/******Bit Index Tree************/struct Tree{int tree[N<<2];void init(){memset(tree, 0, sizeof tree);}inline int low(int x){return x & -x;}void Add(int i, int x){for(; i<=n; i+=low(i)) tree[i]+=x;}int sum(int p){int res = 0;for(int i=p; i>0; i-=low(i)) res+=tree[i];return res;}int query(int l, int r){if (l > r) swap(l, r);return sum(r) – sum(l-1);}} Td, Tsum;/**********End Tree**********/inline int get_sum(int u, int v){int f1 = top[u], f2 = top[v];int tmp = 0;int sum, d;while(f1 – f2){if(dep[f1] < dep[f2]){swap(f1 ,f2);swap(u, v);}sum += Tsum.query(p[f1], p[u]);d += Td.query(p[f1], p[u]);u = fa[f1];f1 = top[u];}sum += Tsum.query(p[u], p[v]);d += Td.query(p[u], p[v]);return sum – d;}vector<int> vi[N]; /// vi[i] 存储以 i 为端点LCA的链编号int d[N], sum[N];void init(){pos =0 ;mm = 0;memset(head,-1,sizeof head);memset(son, -1, sizeof son);for (int i=0;i<N;i++) vi[i].clear();Tsum.init();Td.init();memset(d ,0 , sizeof d);}void DP(int u, int fa = 1){sum[u] = 0;for (int i=head[u];~i;i=e[i].next){int v = e[i].v;if (v==fa) continue;DP(v, u);sum[u] += d[v];}d[u] = sum[u];Tsum.Add(p[u], sum[u]);for (int p : vi[u]) {int a = chain[p].u;int b = chain[p].v;int w = chain[p].w;d[u] = max(d[u], w + get_sum(a, b));}Td.Add(p[u], d[u]);}int main(){int re;scanf("%d", &re);while (re–){scanf("%d%d", &n, &m);init();for (int i=0; i<n-1; i++){int u, v;scanf("%d%d", &u, &v);add(u, v);add(v, u);}gao();for (int i=0; i<m; i++){int u, v , w;scanf("%d%d%d", &u, &v, &w);lca[i] = LCA(u,v);vi[lca[i]].push_back(i);chain[i] = P(u, v, w);}DP(1, 1);printf("%d\n", d[1]);}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
奢侈地享受旅不问人，行随己意的潇洒。
