P2015 Cây nhị phân táo

(f_{u,i}) thể hiện giá trị lớn nhất khi giữ lại i cạnh trong cây con gốc tại u.

(f_{u,i}=max{f_{v,j}+f{u,i-j-1}+w})

#include<cmath>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 210
#define maxm 300000
#define INF 0x3f3f3f3f

using namespace std;

bool tham[maxn];
int n,m,s,t,tot=0,kq,ans;
int dp[maxn][maxn],head[maxn],kichThuoc[maxn];
struct canh{int dau,cuoi,trongSo,keTiep;}e[maxm];

int nhap(){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
    return s*w;
}

void themCanh(int dau,int cuoi,int trongSo){
    e[++tot].dau=dau;e[tot].cuoi=cuoi;
    e[tot].keTiep=head[dau];e[tot].trongSo=trongSo;
    head[dau]=tot;
}

void duyetDFS(int u, int cha){
    for(int i=head[u];i;i=e[i].keTiep){
        int v = e[i].cuoi;
        if(v == cha) continue;
        duyetDFS(v, u);
        kichThuoc[u] += kichThuoc[v] + 1;
        for(int j = min(kichThuoc[u], m); j >= 1; j--)
            for(int k = min(kichThuoc[v], j-1); k >= 0; k--)
                dp[u][j] = max(dp[u][j], dp[u][j-k-1] + dp[v][k] + e[i].trongSo);
    }
}

int main(){
    n=nhap();m=nhap();
    for(int i=1, dau, cuoi, trongSo; i<n; i++){
        dau=nhap();cuoi=nhap();trongSo=nhap();
        themCanh(dau,cuoi,trongSo);themCanh(cuoi,dau,trongSo); 
    }
    duyetDFS(1,0);
    printf("%d\n",dp[1][m]); 
    return 0;
}

P4281 [AHOI2008] Hội họp khẩn cấp

Tìm LCA từng cặp, ta sẽ chỉ có hai trường hợp.

Sau khi phân tích, ta thấy trường hợp không chia sẻ LCA sẽ cho kết quả nhỏ hơn.

#include<cmath>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 2100000
#define maxm 100100
#define INF 0x3f3f3f3f
#define int long long

using namespace std;

int giaTri[maxn];
int n,m,tot,root;
int doSau[maxn],conMax[maxn],cha[maxn];
int top[maxn],kichThuoc[maxn],head[maxn];
struct canh{int dau,cuoi,keTiep;}e[maxn];

int nhap(){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
    return s*w;
}

void themCanh(int dau, int cuoi){
    e[++tot].dau=dau;e[tot].cuoi=cuoi;
    e[tot].keTiep=head[dau];
    head[dau]=tot;
}

void duyetDFS1(int u, int chaBo){
    cha[u]=chaBo;doSau[u]=doSau[chaBo]+1;kichThuoc[u]=1;
    for(int i=head[u];i;i=e[i].keTiep){
        int v=e[i].cuoi;
        if(v==chaBo) continue;
        duyetDFS1(v,u);kichThuoc[u]+=kichThuoc[v];
        if(kichThuoc[v]>kichThuoc[conMax[u]]) conMax[u]=v;
    }
}

void duyetDFS2(int u, int dinh){
    top[u]=dinh;
    if(conMax[u]) duyetDFS2(conMax[u],dinh);
    for(int i=head[u];i;i=e[i].keTiep){
        int v=e[i].cuoi;
        if(v==cha[u]||v==conMax[u]) continue;
        duyetDFS2(v,v);
    }
}

int timLCA(int x, int y){
    while(top[x]!=top[y]){
        if(doSau[top[x]]<doSau[top[y]]) swap(x,y);
        x=cha[top[x]];
    }
    return doSau[x]<doSau[y]?x:y;
}

signed main(){
    n=nhap();m=nhap();
    for(int i=1, dau, cuoi; i<n; i++){
        dau=nhap();cuoi=nhap();
        themCanh(dau,cuoi);themCanh(cuoi,dau);
    }
    duyetDFS1(1,0);duyetDFS2(1,1);
    for(int i=1,x,y,z;i<=m;i++){
        x=nhap();y=nhap();z=nhap();
        if(timLCA(x,y)==timLCA(y,z)&&timLCA(x,y)==timLCA(x,z)){
            int Lca=timLCA(x,y);
            printf("%lld %lld\n",Lca,doSau[x]+doSau[y]+doSau[z]-3*doSau[Lca]);
        }
        else{
            int Lcaxy=timLCA(x,y),Lcayz=timLCA(y,z),Lcaxz=timLCA(x,z),hienTai=-1,id;
            hienTai=max(doSau[Lcaxy],max(doSau[Lcayz],max(doSau[Lcaxz],hienTai)));
            if(hienTai==doSau[Lcaxy]) id=Lcaxy;
            else if(hienTai==doSau[Lcayz]) id=Lcayz;
            else id=Lcaxz;
            int LCAx=timLCA(id,x),LCAy=timLCA(id,y),LCAz=timLCA(id,z);
            printf("%lld %lld\n",id,doSau[x]+doSau[y]+doSau[z]+3*hienTai-2*(doSau[LCAx]+doSau[LCAy]+doSau[LCAz]));
        }
    }
    return 0;
}

P3629 [APIO2010] Tuần tra

Khi k=1, ta chỉ cần nối hai đầu của đường kính cây.

Khi k=2, ta nối đường kính cây đầu tiên, sau đó loại bỏ đường kính này và thực hiện lại việc nối đường kính thứ hai.

Theo phương pháp tìm đường kính cây, ta có thể thay đổi trọng số các cạnh trên đường kính thành số âm trong lần thứ hai.

#include<bits/stdc++.h>
#define maxn 100010 
using namespace std;

int nhap(){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
    return s*w;
}

int duongKinh1,duongKinh2,n,k,dinh,cnt,ans;
int cha[maxn],doSau[maxn],tham[maxn];
int khoangCach[maxn],dinhDau[maxn],head[maxn];
struct node{int dinhKe,w,keTiep;}e[maxn];

void themCanh(int a, int b, int c){
    e[++cnt].dinhKe=b;
    e[cnt].keTiep=head[a];
    head[a]=cnt;
    e[cnt].w=1;
}

void BFS(int x, int ck){
    memset(khoangCach,0,sizeof(khoangCach));
    memset(dinhDau,0,sizeof(dinhDau));
    queue<int >q;q.push(x);dinhDau[x]=1;
    while(!q.empty()){
        int now=q.front();q.pop();
        for(int i=head[now];i;i=e[i].keTiep){
            int y=e[i].dinhKe;
            if(!dinhDau[y]){
                dinhDau[y]=1;
                khoangCach[y]=khoangCach[now]+e[i].w;
                q.push(y);if(ck)cha[y]=now;
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(ans<khoangCach[i])ans=khoangCach[i],dinh=i;
    }
}

void thayDoi(int a){
    while(cha[a]){
        int chaNode=cha[a];
        for(int i=head[chaNode];i;i=e[i].keTiep)
                if(e[i].dinhKe==a){e[i].w=-1;break;}
        for(int i=head[a];i;i=e[i].keTiep){
            if(e[i].dinhKe==chaNode){e[i].w=-1;break;}
        }
        a=chaNode;
    }
}

void tinhDP(int x){
    tham[x]=1;
    for(int i=head[x];i;i=e[i].keTiep){
        int y=e[i].dinhKe;
        if(tham[y])continue;tinhDP(y);
        ans=max(ans,khoangCach[x]+khoangCach[y]+e[i].w);
        khoangCach[x]=max(khoangCach[x],khoangCach[y]+e[i].w);
    }

}

int main(){
    n=nhap();k=nhap(); 
    for(int i=1,a,b;i<n;i++){
        a=nhap();b=nhap();
        themCanh(a,b,1);themCanh(b,a,1);
    }
    if(k==1){
        BFS(1,0);
        BFS(dinh,0);
        printf("%d",2*n-khoangCach[dinh]-1);
    }
    else{
        BFS(1,0);
        BFS(dinh,1);
        duongKinh1=khoangCach[dinh];
        thayDoi(dinh);
        memset(khoangCach,0,sizeof(khoangCach));
        memset(dinhDau,0,sizeof(dinhDau));
        ans=0;
        tinhDP(1);
        printf("%d",2*n-ans-duongKinh1);
    }
    return 0;
}