HDU 5293 Tree chain problem

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5293

题意:有一棵树,树的节点编号为1,2,…,n,树上有m条路,每条路有1个权值,现在要从这些路径中选一些,选出的路径不能有公共点,求这些路径的权值和最大是多少。

思路:待Update。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define MOD 1e9+7
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=100100+5;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
template<typename T> inline T gcd(T&a,T&b){return b==0?a:gcd(b,a%b);}
template<typename T> inline T lcm(T&a,T&b){return a/gcd(a,b)*b;}
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
struct Node{
    int u,v,w;
    Node(int u=0,int v=0,int w=0):u(u),v(v),w(w){}
};
int T,n,m,dfs_clock;
int pnt[maxn],fa[maxn],son[maxn],bel[maxn],sz[maxn],id[maxn],dep[maxn];
vector<int>G[maxn],q[maxn],w[maxn];
vector<Node>chain[maxn];
bool vis[maxn];
int Find(int x){return pnt[x]==x?x:pnt[x]=Find(pnt[x]);}
void Tarjan(int u){
    pnt[u]=u;
    vis[u]=1;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (vis[v]) continue;
        Tarjan(v);
        pnt[v]=u;
    }
    for (int i=0;i<(int)q[u].size();i++){
        int v=q[u][i];
        if (vis[v]){
            int lca=Find(v);
            chain[lca].push_back(Node(u,v,w[u][i]));
        }
    }
}
void dfs1(int u,int f){
    dep[u]=(f==-1?1:dep[f]+1);
    fa[u]=f;
    sz[u]=1;
    son[u]=-1;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==f) continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if (son[u]==-1 || sz[v]>sz[son[u]]){
            son[u]=v;
        }
    }
}
void dfs2(int u,int f){
    bel[u]=f;
    id[u]=++dfs_clock;
    if (son[u]==-1) return;
    dfs2(son[u],f);
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==fa[u] || v==son[u]) continue;
        dfs2(v,v);
    }
}
int sum[maxn];
void init(){
    dfs_clock=0;
    memset(vis,false,sizeof(vis));
    memset(sum,0,sizeof(sum));
    for (int i=1;i<=n;i++) G[i].clear();
    for (int i=1;i<=n;i++) q[i].clear();
    for (int i=1;i<=n;i++) w[i].clear();
    for (int i=1;i<=n;i++) chain[i].clear();
}
int lowbit(int x){return x&(-x);}
void add(int x,int v){
    while (x<=n){
        sum[x]+=v;
        x+=lowbit(x);
    }
}
int Sum(int x){
    int ret=0;
    while (x>0){
        ret+=sum[x];
        x-=lowbit(x);
    }
    return ret;
}
int cal(int u,int v){
    int ans=0;
    while (dep[bel[u]]>dep[bel[v]]){
        ans+=Sum(id[u])-Sum(id[bel[u]]-1);
        u=fa[bel[u]];
    }
    if (dep[u]>dep[v]) ans+=Sum(id[u])-Sum(id[v]);
    return ans;
}
int sumv[maxn],dp[maxn];
void dfs3(int u,int f){
    sumv[u]=0;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==f) continue;
        dfs3(v,u);
        sumv[u]+=dp[v];
    }
    dp[u]=sumv[u];
    for (int i=0;i<(int)chain[u].size();i++){
        Node &t=chain[u][i];
        int tmp=cal(t.u,u)+cal(t.v,u)+sumv[u]+t.w;
        dp[u]=max(dp[u],tmp);
    }
    add(id[u],sumv[u]-dp[u]);
}
int main(){
    for (read(T);T;T--){
        read(n),read(m);
        init();
        for (int i=1;i<n;i++){
            int u,v;read(u),read(v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        for (int i=1;i<=m;i++){
            int u,v,c;read(u),read(v),read(c);
            q[u].push_back(v);
            q[v].push_back(u);
            w[u].push_back(c);
            w[v].push_back(c);
        }
        Tarjan(1);
        dfs1(1,-1);
        dfs2(1,1);
        dfs3(1,-1);
        printf("%d\n",dp[1]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注