【HDU 5233】Tree chain problem （树形DP+树剖+线段树|树状数组）最大权不相交树链集

【题目】

Tree chain problem

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

Sample Output

6

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

Author

FZUACM

Source

2015 Multi-University Training Contest 1

【题意】

　　给一些数链，每个数链有权值，找最权值最大的互不相交数链集。

【分析】

　　怎么说，其实不是很难。

　　TreeDP，f[i]表示i的子树的答案，然后考虑i上面是否有链（如果有，只考虑i为lca的树链）

　　有两种可能，第一种：第i个节点上不出现链，那么dp[i] = ∑(dp[k] | k为i的子节点)；

第二种：第i个节点上出现链，如果选择加入这条链，那么dp[i] = w(链的权值) + ∑(dp[k] | k为链上的节点的子节点) = w + ∑(sum[k] | k为链上的节点 ) - ∑(dp[k] | k为链上的节点) 。sum[i]表示i节点的所有子节点的dp和，在 ∑(sum[k] | k为链上的节点 ) - ∑(dp[k] | k为链上的节点) 中减去的dp[k]会由它的父节点的sum补全。这样就得到了状态转移公式。

转自：http://blog.csdn.net/winddreams/article/details/47004187

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<cmath>
  7 #include<vector>
  8 using namespace std;
  9 #define Maxn 100010
 10 
 11 struct node
 12 {
 13     int x,y,next;
 14 }t[Maxn*2];int len;
 15 int first[Maxn];
 16 
 17 void ins(int x,int y)
 18 {
 19     t[++len].x=x;t[len].y=y;
 20     t[len].next=first[x];first[x]=len;
 21 }
 22 
 23 int mymax(int x,int y) {return x>y?x:y;}
 24 
 25 int nx[Maxn],ny[Maxn],w[Maxn];
 26 
 27 int dfn[Maxn],sm[Maxn],dep[Maxn],son[Maxn],fa[Maxn];
 28 int cnt;
 29 void dfs1(int x,int f)
 30 {
 31     dep[x]=dep[f]+1;fa[x]=f;
 32     sm[x]=1;
 33     for(int i=first[x];i;i=t[i].next) if(t[i].y!=f)
 34     {
 35         int y=t[i].y;
 36         dfs1(y,x);
 37         sm[x]+=sm[y];
 38         if(sm[y]>sm[son[x]]) son[x]=y;
 39     }
 40 }
 41 
 42 int n,m;
 43 int tp[Maxn];
 44 void dfs2(int x,int f,int tpp)
 45 {
 46     dfn[x]=++cnt;tp[x]=tpp;
 47     if(son[x]) dfs2(son[x],x,tpp);
 48     for(int i=first[x];i;i=t[i].next) if(t[i].y!=f&&t[i].y!=son[x])
 49         dfs2(t[i].y,x,t[i].y);
 50 }
 51 
 52 int c[Maxn];
 53 vector<int > v[Maxn];
 54 
 55 int add(int x,int y)
 56 {
 57     for(int i=x;i<=n;i+=i&(-i))
 58         c[i]+=y;
 59 }
 60 
 61 int query(int l,int r)
 62 {
 63     int ans=0;
 64     for(int i=r;i>=1;i-=i&(-i))
 65         ans+=c[i];
 66     l--;
 67     for(int i=l;i>=1;i-=i&(-i))
 68         ans-=c[i];
 69     return ans;
 70 }
 71 
 72 int gans(int x,int y,int p)
 73 {
 74     int ans=0,tt;
 75     while(tp[x]!=tp[y])
 76     {
 77         if(dep[tp[x]]<dep[tp[y]]) tt=x,x=y,y=tt;
 78         if(p==1) ans+=query(dfn[tp[x]],dfn[x]);
 79         x=fa[tp[x]];
 80     }
 81     if(dep[x]<dep[y]) tt=x,x=y,y=tt;
 82     if(p==1)
 83     {
 84         ans+=query(dfn[y],dfn[x]);
 85         return ans;
 86     }
 87     else return y;
 88 }
 89 
 90 int sum[Maxn],g[Maxn],lca[Maxn];
 91 void ffind(int x,int f)
 92 {
 93     sum[x]=g[x]=0;
 94     for(int i=first[x];i;i=t[i].next) if(t[i].y!=f)
 95     {
 96         ffind(t[i].y,x);
 97         sum[x]+=g[t[i].y];
 98     }
 99     add(dfn[x],sum[x]);
100     g[x]=sum[x];
101     for(int i=0;i<v[x].size();i++)
102     {
103         int now=gans(nx[v[x][i]],ny[v[x][i]],1);
104         g[x]=mymax(g[x],now+w[v[x][i]]);
105     }
106     add(dfn[x],-g[x]);
107 }
108 
109 int main()    
110 {
111     int T;
112     scanf("%d",&T);
113     while(T--)
114     {
115         scanf("%d%d",&n,&m);
116         len=0;
117         memset(first,0,sizeof(first));
118         for(int i=1;i<n;i++)
119         {
120             int x,y;
121             scanf("%d%d",&x,&y);
122             ins(x,y);ins(y,x);
123         }
124         dep[0]=0;
125         memset(son,0,sizeof(son));
126         dfs1(1,0);cnt=0;
127         dfs2(1,0,1);
128         for(int i=1;i<=n;i++) v[i].clear();
129         for(int i=1;i<=m;i++)
130         {
131             scanf("%d%d%d",&nx[i],&ny[i],&w[i]);
132             lca[i]=gans(nx[i],ny[i],0);
133             v[lca[i]].push_back(i);
134         }
135         memset(c,0,sizeof(c));
136         ffind(1,0);
137         printf("%d
",g[1]);
138     }
139     return 0;
140 }

View Code

2016-11-10 19:56:36