﻿ HDU5293(SummerTrainingDay13-B Tree DP + 树状数组 + dfs序)

# Tree chain problem

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1798    Accepted Submission(s): 585

### 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

1 7 3 1 2 1 3 2 4 2 5 3 6 3 7 2 3 4 4 5 3 6 7 3

6

### Hint

Stack expansion program： #pragma comment(linker, "/STACK:1024000000,1024000000")

FZUACM

### Source

```  1 //2017-09-13
2 #include <cstdio>
3 #include <cstring>
4 #include <iostream>
5 #include <algorithm>
6 #include <vector>
7 #pragma comment(linker, "/STACK:1024000000,1024000000")
8
9 using namespace std;
10
11 const int N = 210000;
12 const int LOG_N = 22;
13
14 int head[N], tot;
15 struct Edge{
16     int v, next;
17 }edge[N<<1];
18
19 void add_edge(int u, int v){
20     edge[tot].v = v;
21     edge[tot].next = head[u];
22     head[u] = tot++;
23 }
24
25 int in[N], out[N], idx, depth[N], father[N][LOG_N];
26 void dfs(int u, int fa){
27     in[u] = ++idx;
28     for(int i = head[u]; i != -1; i = edge[i].next){
29         int v = edge[i].v;
30         if(v == fa)continue;
31         depth[v] = depth[u]+1;
32         father[v][0]= u;
33         for(int j = 1; j < LOG_N; j++)
34           father[v][j] = father[father[v][j-1]][j-1];
35         dfs(v, u);
36     }
37     out[u] = ++idx;
38 }
39
40 int tree[N];
41
42 int lowbit(int x){
43     return x&(-x);
44 }
45
46 void add(int pos, int val){
47     for(int i = pos; i <= N; i+=lowbit(i))
48       tree[i] += val;
49 }
50
51 int query(int l){
52     int sum = 0;
53     for(int i = l; i > 0; i-=lowbit(i))
54       sum += tree[i];
55     return sum;
56 }
57
58 int lca(int u, int v){
59     if(depth[u] < depth[v])
60       swap(u, v);
61     for(int i = LOG_N-1; i >= 0; i--){
62         if(depth[father[u][i]] >= depth[v])
63           u = father[u][i];
64     }
65     if(u == v)return u;
66     for(int i = LOG_N-1; i >= 0; i--){
67         if(father[u][i] != father[v][i]){
68             u = father[u][i];
69             v = father[v][i];
70         }
71     }
72     return father[u][0];
73 }
74 struct Chain{
75     int u, v, w;
76 }chain[N];
77 vector<int> vec[N];
78
79 int dp[N], sum[N];
80 void solve(int u, int fa){
81     dp[u] = sum[u] = 0;
82     for(int i = head[u]; i != -1; i = edge[i].next){
83         int v = edge[i].v;
84         if(v == fa)continue;
85         solve(v, u);
86         sum[u] += dp[v];
87     }
88     dp[u] = sum[u];
89     for(auto &pos: vec[u]){
90         int a = chain[pos].u;
91         int b = chain[pos].v;
92         int c = chain[pos].w;
93         dp[u] = max(dp[u], sum[u]+query(in[a])+query(in[b])+c);
94     }
97 }
98
99 int T, n, m;
100 void init(){
101     tot = 0;
102     idx = 0;
103     depth[1] = 1;
104     for(int i = 1; i <= n; i++)
105       vec[i].clear();
107     memset(dp, 0, sizeof(0));
108     memset(sum, 0, sizeof(0));
109     memset(tree, 0, sizeof(tree));
110 }
111
112 int main()
113 {
114     freopen("inputB.txt", "r", stdin);
115     scanf("%d", &T);
116     while(T--){
117         scanf("%d%d", &n, &m);
118         init();
119         int u, v;
120         for(int i = 0; i < n-1; i++){
121             scanf("%d%d", &u, &v);
124         }
125         dfs(1, 0);
126         for(int i = 0; i < m; i++){
127             scanf("%d%d%d", &chain[i].u, &chain[i].v, &chain[i].w);
128             vec[lca(chain[i].u, chain[i].v)].push_back(i);
129         }
130         solve(1, 0);
131         printf("%d
", dp[1]);
132     }
133
134     return 0;
135 }```