【题目】
Tree chain problem
Problem DescriptionCoco 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 pickInputThe 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.OutputFor each tests:
A single integer, the maximum number of paths.Sample Input1
7 3
1 2
1 3
2 4
2 5
3 6
3 7
2 3 4
4 5 3
6 7 3Sample Output6HintStack expansion program： #pragma comment(linker, "/STACK:1024000000,1024000000")
AuthorFZUACMSource
【题意】
给一些数链，每个数链有权值，找最权值最大的互不相交数链集。
【分析】
怎么说，其实不是很难。
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补全。这样就得到了状态转移公式。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
#define Maxn 100010 struct node
{
int x,y,next;
}t[Maxn*];int len;
int first[Maxn]; void ins(int x,int y)
{
t[++len].x=x;t[len].y=y;
t[len].next=first[x];first[x]=len;
} int mymax(int x,int y) {return x>y?x:y;} int nx[Maxn],ny[Maxn],w[Maxn]; int dfn[Maxn],sm[Maxn],dep[Maxn],son[Maxn],fa[Maxn];
int cnt;
void dfs1(int x,int f)
{
dep[x]=dep[f]+;fa[x]=f;
sm[x]=;
for(int i=first[x];i;i=t[i].next) if(t[i].y!=f)
{
int y=t[i].y;
dfs1(y,x);
sm[x]+=sm[y];
if(sm[y]>sm[son[x]]) son[x]=y;
}
} int n,m;
int tp[Maxn];
void dfs2(int x,int f,int tpp)
{
dfn[x]=++cnt;tp[x]=tpp;
if(son[x]) dfs2(son[x],x,tpp);
for(int i=first[x];i;i=t[i].next) if(t[i].y!=f&&t[i].y!=son[x])
dfs2(t[i].y,x,t[i].y);
} int c[Maxn];
vector<int > v[Maxn]; int add(int x,int y)
{
for(int i=x;i<=n;i+=i&(-i))
c[i]+=y;
} int query(int l,int r)
{
int ans=;
for(int i=r;i>=;i-=i&(-i))
ans+=c[i];
l--;
for(int i=l;i>=;i-=i&(-i))
ans-=c[i];
return ans;
} int gans(int x,int y,int p)
{
int ans=,tt;
while(tp[x]!=tp[y])
{
if(dep[tp[x]]<dep[tp[y]]) tt=x,x=y,y=tt;
if(p==) ans+=query(dfn[tp[x]],dfn[x]);
x=fa[tp[x]];
}
if(dep[x]<dep[y]) tt=x,x=y,y=tt;
if(p==)
{
ans+=query(dfn[y],dfn[x]);
return ans;
}
else return y;
} int sum[Maxn],g[Maxn],lca[Maxn];
void ffind(int x,int f)
{
sum[x]=g[x]=;
for(int i=first[x];i;i=t[i].next) if(t[i].y!=f)
{
ffind(t[i].y,x);
sum[x]+=g[t[i].y];
}
add(dfn[x],sum[x]);
g[x]=sum[x];
for(int i=;i<v[x].size();i++)
{
int now=gans(nx[v[x][i]],ny[v[x][i]],);
g[x]=mymax(g[x],now+w[v[x][i]]);
}
add(dfn[x],-g[x]);
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
len=;
memset(first,,sizeof(first));
for(int i=;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
dep[]=;
memset(son,,sizeof(son));
dfs1(,);cnt=;
dfs2(,,);
for(int i=;i<=n;i++) v[i].clear();
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&nx[i],&ny[i],&w[i]);
lca[i]=gans(nx[i],ny[i],);
v[lca[i]].push_back(i);
}
memset(c,,sizeof(c));
ffind(,);
printf("%d\n",g[]);
}
return ;
}
2016-11-10 19:56:36