HDU 5293 트 리 체인 문제 [트 리 체인 분할 + 선분 트 리 + 트 리 DP]

5460 단어 동적 계획 - 트 리 DP데이터 구조 - 트 리 체인 분할데이터 구조-선분 트 리
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 
제목: N 개의 점 을 주 는 나무, M 개의 나무 사슬, 나무 사슬 은 권리 가 있 습 니 다. 꺼 낸 나무 사슬 이 서로 교차 하지 않 는 상황 에서 가중치 와 최대 가 얼마 인지 물 어보 세 요.
해법: 이렇게 고려 할 수 있 습 니 다. 만약 에 어떤 점 이 X, Y 의 LCA 로 서 이 체인 을 취하 면 그 서브 트 리 의 해 는 최대 얼마 입 니까?
DP [x] 를 설정 하면 x 를 뿌리 로 하 는 하위 트 리 에서 이 점 을 lca 로 하 는 체인 을 제거 한 후 얻 을 수 있 는 최대 치 를 표시 합 니 다.그러면 알 수 있 듯 이 특정한 체인 을 가 져 온 후에 (이 체인 의 lca 는 x) 얻 을 수 있 는 최대 치 는?Σ DP [{son}] + W 그 중 {son} 은 이 체인 의 아들 집합 (체인 자 체 를 포함 하지 않 음) 입 니 다. dfs 에서 특정한 점 x 까지 x 점 을 lca 로 하 는 모든 체인 을 처리 하고 모든 체인 에서 얻 을 수 있 는 값 의 최대 치 를 계산 하여 dp [X] 에 할당 할 수 있 습 니 다.
그럼 어떻게 구 해 요?Σ DP[{son}] ? 우 리 는 이렇게 처리 할 수 있다. 매번 dp [X] 를 구 할 때마다 - dp [X] 를 X 점 에 추가 하 는 VAL [], + dp [X] 를 X 점 에 추가 하 는 아버지의 VAL [] 을 구 할 수 있다. 그러면Σ VAL [체인 의 점] 이 바로 원 하 는 답 입 니 다.분명 한 것 은 체인 상의 점 권 과 트 리 체인 으로 나 눌 수 있 는 + 선분 트 리 로 쓸 수 있 고 복잡 도 는 N * logN * logN 이다.(실제로 이 문 제 는 수정 되 지 않 았 기 때문에 DFS 순서 + 트 리 배열 로 O (N * logN) 를 빠르게 처리 할 수 있 습 니 다)
코드: (ZKW 선분 트 리 1200 + MS)
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#pragma comment(linker, "/STACK:1024000000,1024000000")
template 
bool scanff(T &ret){ //Faster Input
    char c; int sgn; T bit=0.1;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&c!='.'&&(c'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    if(c==' '||c=='
'){ ret*=sgn; return 1; }
    while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;
    ret*=sgn;
    return 1;
}
#define inf 1073741823
#define llinf 4611686018427387903LL
#define PI acos(-1.0)
#define lth (th<<1)
#define rth (th<<1|1)
#define rep(i,a,b) for(int i=int(a);i<=int(b);i++)
#define drep(i,a,b) for(int i=int(a);i>=int(b);i--)
#define gson(i,root) for(int i=ptx[root];~i;i=ed[i].next)
#define tdata int testnum;scanff(testnum);for(int cas=1;cas<=testnum;cas++)
#define mem(x,val) memset(x,val,sizeof(x))
#define mkp(a,b) make_pair(a,b)
#define findx(x) lower_bound(b+1,b+1+bn,x)-b
#define pb(x) push_back(x)
using namespace std;
typedef long long ll;
typedef pair pii;

#define NN 100100

struct node{
    int x,y,w;
}a[NN];
vector q[NN];
int son[NN],sz[NN],top[NN],pos[NN],dep[NN],f[NN][20],pn;
int ptx[NN],lnum,dp[NN];
int n,qn;
struct edge{
    int v,next;
    edge(){}
    edge(int v,int next){
        this->v=v;
        this->next=next;
    }
}ed[NN*2];
void addline(int x,int y){
    ed[lnum]=edge(y,ptx[x]);
    ptx[x]=lnum++;
}
void init(int n){
    pn=lnum=0;
    rep(i,1,n)ptx[i]=-1;
    rep(i,1,n)q[i].clear();
}
//tree chain divide
int getson(int x,int fa){
    int val=0;
    son[x]=0;
    sz[x]=1;
    f[x][0]=fa;
    dep[x]=dep[fa]+1;
    gson(i,x){
        int y=ed[i].v;
        if(y==fa)continue;
        sz[x]+=getson(y,x);
        if(sz[y]>val){
            val=sz[y];
            son[x]=y;
        }
    }
    return sz[x];
}
void getchain(int r,int x,int fa){
    top[x]=r;
    pos[x]=++pn;
    if(son[x])getchain(r,son[x],x);
    gson(i,x){
        int y=ed[i].v;
        if(y==fa||y==son[x])continue;
        getchain(y,y,x);
    }
}
int lca(int x,int y){
    if(dep[x]=dep[y])x=f[x][i];
    if(x==y)return x;
    drep(i,16,0)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}
//segment tree
int m,val[NN*4];
void build(int n){
    for(m=1;m>=1,r>>=1){
        if(~l&1)sum+=val[l^1];
        if(r&1) sum+=val[r^1];
    }
    return sum;
}
inline void update(int pos,int v){
    for(pos=pos+m;pos;pos>>=1)val[pos]+=v;
}
//solve
void calc(int z){
    int sz=q[z].size()-1;
    rep(i,0,sz){
        int x=q[z][i].x;
        int y=q[z][i].y;
        int w=q[z][i].w;
        while(top[x]!=top[y]){
            if(dep[top[x]]dep[y])swap(x,y);
        w+=query(pos[x],pos[y]);
        dp[z]=max(w,dp[x]);
    }
    update(pos[z],-dp[z]);
    if(f[z][0])update(pos[f[z][0]],dp[z]);
}
void solve(int x,int fa){
    dp[x]=0;
    gson(i,x){
        int y=ed[i].v;
        if(y==fa)continue;
        solve(y,x);
        dp[x]+=dp[y];
    }
    calc(x);
}
int main(){
    tdata{
        scanff(n);scanff(qn);
        init(n);
        build(n);
        rep(i,1,n-1){
            int x;scanff(x);
            int y;scanff(y);
            addline(x,y);
            addline(y,x);
        }
        getson(1,0);
        getchain(1,1,0);
        rep(k,1,16)
        rep(i,1,n)f[i][k]=f[f[i][k-1]][k-1];
        rep(i,1,qn){
            scanff(a[i].x);
            scanff(a[i].y);
            scanff(a[i].w);
            q[lca(a[i].x,a[i].y)].pb(a[i]);
        }
        solve(1,0);
        printf("%d
",dp[1]);
    }
}
백그라운드 내 보 내기
django session 구현

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage