HDU 5293(SummerTrainingDay 13-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
 
 
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
 
 
Sample Output
6
Hint Stack expansion program: #pragma comment(linker, "/STACK:1024000000,1024000000")
 
 
Author
FZUACM
 
 
Source
2015 Multi-University Training Contest 1
 
各チェーンu,v,wについてlca(u,v)の頂点のみで処理する
dp[i]にiを根とするサブツリーの最大値を表し、sum[i]にdp[vi]を表す和(viをiとする息子たち)
i点には2つの決定があり、1つはiをlcaとしないチェーンであり、dp[i]=sum[i]である.
もう1つはiをlcaとするチェーンを選択し、転移方程式がある:dp[i]=sigma(dp[vj])+sigma(sum[kj])+w.(sigmaは累積を表し、vjはチェーン上にいない子供たちを表し、kjはチェーン上にいる子供たちを表す)
計算を容易にするために,dp[i]=sum[i]−sigma(dp[k]−sum[k])+w=sum[i]+sigma(sum[k]−dp[k])+wを処理した.
dfsシーケンスとツリー配列を用いてsigma(sum[k]−dp[k])をlognで算出した.

  1 //2017-09-13
  2 #include 
  3 #include 
  4 #include 
  5 #include 
  6 #include 
  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     }
 95     add(in[u], sum[u]-dp[u]);
 96     add(out[u], dp[u]-sum[u]);
 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();
106     memset(head, -1, sizeof(head));
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);
122             add_edge(u, v);
123             add_edge(v, u);
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 }

 
転載先:https://www.cnblogs.com/Penn000/p/7517896.html