[题意]
给定一颗树上的几条链和每条链的权值,求能取出的不含有公共节点的链的最大权值….
[解]
预处理每条链的lca
树形DP, d[i]表示取到这个节点时可以得到的最大值 , sum[i]=sigma( d[k] | k 是i的子节点)
如果不取i d[i]=sum[i]
如果取i , e是lca为i的链则 d[i]=max(d[i],e的权值+sigma(sum[k])-sigma(d[k])) k为树链上的点
可以用树链剖分+树装数组在nlogn的时间复杂度内求链上的值
Tree chain problemTime Limit: 6000/3000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 430Accepted Submission(s): 114
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
Recommend
We have carefully selected several similar problems for you:52995298529752955294
/* ***********************************************Author:CKbossCreated Time :2015年07月22日 星期三 15时46分03秒File Name:HDOJ5293.cpp************************************************ */#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <cmath>#include <cstdlib>#include <vector>#include <queue>#include <set>#include <map>#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std;const int maxn=100100;int n,m;/**********************CHAIN***********************/struct Chain{int from,to,weight;}chain[maxn];/// chain lca at pos ivector<int> vi[maxn];/**********************EDGE*************************/struct Edge{int to,next;}edge[maxn*2];int Adj[maxn],Size;void init(){memset(Adj,-1,sizeof(Adj)); Size=0;for(int i=0;i<=n;i++) vi[i].clear();}void Add_Edge(int u,int v){edge[Size].to=v;edge[Size].next=Adj[u];Adj[u]=Size++;}/**********************LCA**************************/const int DEG=22;int fa[maxn][DEG];///fa[i][j]i号节点的第2^j的祖先int deg[maxn];///深度void BFS(int root){queue<int> q;deg[root]=0;fa[root][0]=root;q.push(root);while(!q.empty()){int u=q.front(); q.pop();for(int i=1;i<DEG;i++){fa[u][i]=fa[fa[u][i-1]][i-1];}for(int i=Adj[u];~i;i=edge[i].next){int v=edge[i].to;if(v==fa[u][0]) continue;deg[v]=deg[u]+1;fa[v][0]=u;q.push(v);}}}int LCA(int u,int v){if(deg[u]>deg[v]) swap(u,v);int hu=deg[u],hv=deg[v];int tu=u,tv=v;for(int det=hv-hu,i=0;det;i++,det=det/2)if(det&1)tv=fa[tv][i];if(tu==tv) return tu;for(int i=DEG-1;i>=0;i–){if(fa[tu][i]==fa[tv][i])continue;tu=fa[tu][i];tv=fa[tv][i];}return fa[tu][0];}/************************树链剖分******************/int Fa[maxn],deep[maxn],num[maxn],son[maxn];int top[maxn],p[maxn],rp[maxn],pos;int tree1[maxn],tree2[maxn];int ans;void INIT(){init();pos=1; ans=0;memset(son,-1,sizeof(son));memset(tree1,0,sizeof(tree1));memset(tree2,0,sizeof(tree2));}void dfs1(int u,int pre,int d){num[u]=1; Fa[u]=pre; deep[u]=d;for(int i=Adj[u];~i;i=edge[i].next){int v=edge[i].to;if(v==pre) continue;dfs1(v,u,d+1);num[u]+=num[v];if((son[u]==-1)||(num[son[u]]<num[v])) son[u]=v;}}void getPOS(int u,int to){top[u]=to; p[u]=pos++; rp[p[u]]=u;if(son[u]!=-1) getPOS(son[u],to);for(int i=Adj[u];~i;i=edge[i].next){int v=edge[i].to;if(v!=Fa[u]&&v!=son[u]) getPOS(v,v);}}// arrayinline int lowbit(int x) { return x&(-x); }void Add(int* tree,int p,int v){for(int i=p;i<maxn;i+=lowbit(i)) tree[i]+=v;}int _sum(int* tree,int p){int sum=0;for(int i=p;i;i-=lowbit(i)) sum+=tree[i];return sum;}int Query(int* tree,int L,int R){return _sum(tree,R)-_sum(tree,L-1);}// query sum of node on the chainint get_chain_sum(int u,int v){int f1=top[u],f2=top[v];// ret1: sum of sum tree1// ret2: sum of d tree2int ret1=0,ret2=0;while(f1!=f2){if(deep[f1]<deep[f2]) { swap(f1,f2); swap(u,v); }//ret+=ret1+=Query(tree1,p[f1],p[u]);ret2+=Query(tree2,p[f1],p[u]);u=Fa[f1]; f1=top[u];}if(deep[u]>deep[v]) swap(u,v);//ret+=ret1+=Query(tree1,p[u],p[v]);ret2+=Query(tree2,p[u],p[v]);return ret1-ret2;}// add one point on the node of the chainvoid update(int* tree,int x,int v){Add(tree,p[x],v);}int d[maxn],sum[maxn];void DFS(int u,int fa){sum[u]=0;for(int i=Adj[u];~i;i=edge[i].next){int v=edge[i].to;if(v==fa) continue;DFS(v,u);sum[u]+=d[v];}/// not choose u;d[u]=sum[u];update(tree1,u,sum[u]);/// choose ufor(int i=0,sz=vi[u].size();i<sz;i++){int p=vi[u][i];int w=chain[p].weight,from=chain[p].from,to=chain[p].to;int temp=w+get_chain_sum(from,to);d[u]=max(d[u],temp);}if(ans<d[u]) ans=d[u];update(tree2,u,d[u]);}int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout); int T_T;scanf("%d",&T_T);while(T_T–){scanf("%d%d",&n,&m);INIT();for(int i=0,u,v;i<n-1;i++){scanf("%d%d",&u,&v);Add_Edge(u,v); Add_Edge(v,u);}BFS(1);for(int i=0,u,v,w;i<m;i++){scanf("%d%d%d",&u,&v,&w);//chain[i]=(Chain){u,v,w};chain[i].from=u; chain[i].to=v; chain[i].weight=w;int lca=LCA(u,v);vi[lca].push_back(i);}dfs1(1,1,0); getPOS(1,1);DFS(1,1);printf("%d\n",ans);}return 0;}
版权声明：—– from:
即使没有收获的希望也心平气和的继续。
