=-=抓住叶节点往上揪
Tree chain problem
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1752 Accepted Submission(s): 561
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
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.
A single integer, the maximum number of paths.
7 3
1 2
1 3
2 4
2 5
3 6
3 7
2 3 4
4 5 3
6 7 3
Stack expansion program： #pragma comment(linker, "/STACK:1024000000,1024000000")
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=1e5+88;
int fa[maxn],dep[maxn],size[maxn],pos[maxn],bl[maxn],head[maxn];
int sum[maxn];
int dp[maxn],su[maxn],n,m;
vector<int>G[maxn];
struct node{
int to,next;
}edge[maxn<<1];
struct cst{
int x,y,z;
}road[maxn];
int tot,sz;
void init(){
tot=sz=0;
memset(sum,0,sizeof(sum));
memset(head,-1,sizeof(head));
for(int i=1;i<=n;++i) G[i].clear();
}
void add(int u,int v) {
edge[tot].to=v;
edge[tot].next=head[u];
head[u]=tot++;
}
void sadd(int u,int val) {
for( ; u<=n;u+=u&(-u))
sum[u]+=val;
}
int getsum(int u) {
int ret=0;
for(;u;u-=u&(-u))
ret+=sum[u];
return ret;
}
void dfs1(int x){
size[x]=1;
for(int i=head[x];i+1;i=edge[i].next){
int v=edge[i].to;
if(v==fa[x]) continue;
fa[v]=x;
dep[v]=dep[x]+1;
dfs1(v);
size[v]+=size[x];
}
}
void dfs2(int x,int chain)
{
bl[x]=chain;
pos[x]=++sz;
int k=0;
for(int i=head[x];i+1;i=edge[i].next){
int v=edge[i].to;
if(dep[v]>dep[x]&&size[v]>size[k])
k=v;
}
if(!k) return;
dfs2(k,chain);
for(int i=head[x];i+1;i=edge[i].next)
if(dep[edge[i].to]>dep[x]&&edge[i].to!=k)
dfs2(edge[i].to,edge[i].to);
}
int LCA(int x,int y){
while(bl[x]!=bl[y]) {
if(dep[bl[x]]<dep[bl[y]]) swap(x,y);
x=fa[bl[x]];
}
if(pos[x]>pos[y]) swap(x,y);
return x;
}
int query(int x,int y){
int ret=0;
while(bl[x]!=bl[y]){
if(dep[bl[x]]<dep[bl[y]]) swap(x,y);
ret+=getsum(pos[x])-getsum(pos[bl[x]]-1);
x=fa[bl[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ret+=getsum(pos[y])-getsum(pos[x]-1);
return ret;
}
void solve(int u){
su[u]=0;
for(int i=head[u];i+1;i=edge[i].next){
int v=edge[i].to;
if(v==fa[u]) continue;
solve(v);
su[u]+=dp[v];
}
dp[u]=su[u];
for(int i=0;i<(int)G[u].size();++i){
int v=G[u][i];
dp[u]=max(dp[u],query(road[v].x,road[v].y)+su[u]+road[v].z);
}
sadd(pos[u],su[u]-dp[u]);
}
int main(){
int t,u,v;
for(scanf("%d",&t);t--;){
scanf("%d%d",&n,&m);
init();
for(int i=1;i<n;++i){
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
dfs1(1);
dfs2(1,1);
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&road[i].x,&road[i].y,&road[i].z);
G[LCA(road[i].x,road[i].y)].push_back(i);
}
solve(1);
printf("%d\n",dp[1]);
}
}