BZOJ 2599: [IOI2011]Race [点分治]

2599: [IOI2011]Race

Time Limit: 70 Sec Memory Limit: 128 MB
Submit: 3069 Solved: 898
[Submit][Status][Discuss]

Description

给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 1000000

Input

第一行两个整数 n, k
第二..n行每行三个整数表示一条无向边的两端和权值 (注意点的编号从0开始)

Output

一个整数表示最小边数量如果不存在这样的路径输出-1

Sample Input

4 3
0 1 1
1 2 2
1 3 4

Sample Output

小总结：

目前遇到的点分治处理有两种：

1.先统计每颗子树，处理一颗子树时使用了之前子树的信息
2.先统计整棵树然后减去同一棵子树里的，可以只一遍邻接链表循环

对于本题，

1.可以用d[i]表示之前遍历过的子树中深度为i的最小边数，c[i]表示i到根的边数

然后点分治时，一个个子树遍历，先更新答案在用更新d[]，再一遍遍历把d[]复原（不能用memset，复杂度...）

注意：每次dfsSol里都要d[0]=0,难道有w=0的边？！

2.还可以用那种排序的方法，不过区间min不支持减法，所以记录每种边数出现的次数，就可以减了....

注意：排序往里扫的时候是l<=r，为什么啊？明明同一个点，我太弱了不知道为什么

ps：1比2快了10ms

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=2e5+5,K=1e6+5,INF=1e9;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
    return x*f;
}
int n,k,u,v,w;
struct edge{
    int v,w,ne;
}e[N<<1];
int h[N],cnt;
inline void ins(int u,int v,int w){
    cnt++;
    e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;
    cnt++;
    e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;
}

int size[N],f[N],rt,vis[N],sum;
void dfsRt(int u,int fa){
    size[u]=1;f[u]=0;
    for(int i=h[u];i;i=e[i].ne){
        int v=e[i].v;
        if(vis[v]||v==fa) continue;
        dfsRt(v,u);
        size[u]+=size[v];
        f[u]=max(f[u],size[v]);
    }
    f[u]=max(f[u],sum-size[u]);
    if(f[u]<f[rt]) rt=u;
}

int deep[N],d[K],c[N],ans=INF;
void cal(int u,int fa){
    if(deep[u]<=k) ans=min(ans,d[k-deep[u]]+c[u]);
    for(int i=h[u];i;i=e[i].ne){
        int v=e[i].v;
        if(vis[v]||v==fa) continue;
        deep[v]=deep[u]+e[i].w;
        c[v]=c[u]+1;
        cal(v,u);
    }
}
void add(int u,int fa){
    if(deep[u]<=k) d[deep[u]]=min(d[deep[u]],c[u]);
    for(int i=h[u];i;i=e[i].ne){
        int v=e[i].v;
        if(vis[v]||v==fa) continue;
        add(v,u);
    }
}
void recover(int u,int fa){
    if(deep[u]<=k) d[deep[u]]=INF;
    for(int i=h[u];i;i=e[i].ne){
        int v=e[i].v;
        if(vis[v]||v==fa) continue;
        recover(v,u);
    }
}
void dfsSol(int u){//printf("sol %d
",u);
    vis[u]=1;d[0]=0;//must d[0]=0!!!!!!!!!!!!!!!!
    for(int i=h[u];i;i=e[i].ne){
        int v=e[i].v;
        if(vis[v]) continue;
        deep[v]=e[i].w;c[v]=1;
        cal(v,u);
        add(v,u);
    }
    for(int i=h[u];i;i=e[i].ne){
        int v=e[i].v;
        if(vis[v]) continue;
        recover(v,u);
    }
    for(int i=h[u];i;i=e[i].ne){
        int v=e[i].v;
        if(vis[v]) continue;
        sum=size[v];
        rt=0;dfsRt(v,0);v=rt;
        dfsSol(v);
    }
}

int main(){
    //freopen("in.txt","r",stdin);
    n=read();k=read();
    for(int i=1;i<=k;i++) d[i]=INF;
    for(int i=1;i<n;i++) u=read()+1,v=read()+1,w=read(),ins(u,v,w);
    sum=n;
    f[0]=INF;
    rt=0;dfsRt(1,0);
    dfsSol(rt);
    printf("%d",ans==INF?-1:ans);
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=2e5+5,K=1e6+5,INF=1e9;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
    return x*f;
}
int n,k,u,v,w;
struct edge{
    int v,w,ne;
}e[N<<1];
int h[N],cnt;
inline void ins(int u,int v,int w){
    cnt++;
    e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;
    cnt++;
    e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;
}

int size[N],f[N],rt,vis[N],sum;
void dfsRt(int u,int fa){
    size[u]=1;f[u]=0;
    for(int i=h[u];i;i=e[i].ne){
        int v=e[i].v;
        if(vis[v]||v==fa) continue;
        dfsRt(v,u);
        size[u]+=size[v];
        f[u]=max(f[u],size[v]);
    }
    f[u]=max(f[u],sum-size[u]);
    if(f[u]<f[rt]) rt=u;
}

int deep[N],ans[N],c[N];
struct data{
    int deep,c;
    data(int a=0,int b=0):deep(a),c(b){}
    bool operator <(const data &rhs)const{return deep<rhs.deep;}
}a[N];int p;
void dfsDeep(int u,int fa){
    a[++p]=data(deep[u],c[u]);
    for(int i=h[u];i;i=e[i].ne){
        int v=e[i].v;
        if(vis[v]||v==fa) continue;
        deep[v]=deep[u]+e[i].w;c[v]=c[u]+1;
        dfsDeep(v,u);
    }
}
void cal(int u,int nowDeep,int nowC,int v){//printf("cal %d
",u);
    deep[u]=nowDeep;c[u]=nowC;p=0;
    dfsDeep(u,0);
    sort(a+1,a+1+p);
    //for(int i=1;i<=p;i++) printf("a %d %d
",a[i].deep,a[i].c);
    int l=1,r=p;
    while(l<=r){
        while(l<r&&a[l].deep+a[r].deep>k) r--;
        int i=r;
        while(a[l].deep+a[i].deep==k) ans[a[l].c+a[i].c]+=v,i--;
        l++;
    }
}
void dfsSol(int u){//printf("dfsSol %d
",u);
    vis[u]=1;
    cal(u,0,0,1);
    for(int i=h[u];i;i=e[i].ne){
        int v=e[i].v;
        if(vis[v]) continue;
        cal(v,e[i].w,1,-1);
        sum=size[v];
        rt=0;dfsRt(v,0);v=rt;
        dfsSol(v);
    }
}

int main(){
    //freopen("in.txt","r",stdin);
    n=read();k=read();
    for(int i=1;i<n;i++) u=read()+1,v=read()+1,w=read(),ins(u,v,w);
    sum=n;
    f[0]=INF;
    rt=0;dfsRt(1,0);
    dfsSol(rt);
    for(int i=1;i<=n;i++) if(ans[i]) {printf("%d",i);return 0;}
    printf("-1");
}