树分治（挑战p360）

poj1741

题：http://poj.org/problem?id=1741

题意：给定树，和一个树k，问有多少个点对之间的路径是不超过k

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

const ll INF=1e18;

int ans=,tot,maxx,root;

const int M=1e4+;

struct node{

    int v,w,nextt;

}e[M<<];

int head[M],vis[M],sz[M],maxv[M],num,dis[M],n,k;

void addedge(int u,int v,int w){

    e[tot].v=v;

    e[tot].w=w;

    e[tot].nextt=head[u];

    head[u]=tot++;

}

void dfssz(int u,int f){

    sz[u]=;

    maxv[u]=;

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;//cout<<"!!"<<endl;

        if(v==f||vis[v])

            continue;

        dfssz(v,u);

        sz[u]+=sz[v];

        maxv[u]=max(maxv[u],sz[v]);

    }

}

void dfsroot(int r,int u,int f){

    maxv[u]=max(maxv[u],sz[r]-sz[u]);

    if(maxv[u]<maxx){

        maxx=maxv[u];

        root=u;

    }

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(vis[v]||v==f)

            continue;

        dfsroot(r,v,u);

    }

}

void dfsdis(int u,int d,int f){

    dis[num++]=d;

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(v==f||vis[v])

            continue;

        dfsdis(v,d+e[i].w,u);

    }

}

int cal(int u,int d){

    int sum=;

    num=;

    dfsdis(u,d,-);

    sort(dis,dis+num);

    int i=,j=num-;

    while(i<j){

        while(dis[i]+dis[j]>k&&i<j){

            j--;

        }

        sum+=j-i;

        i++;

    }

    return sum;

}

void solve(int u){

    maxx=n;

    dfssz(u,-);

    dfsroot(u,u,-);

    ans+=cal(root,);

    vis[root]=;

    for(int i=head[root];~i;i=e[i].nextt){

        int v=e[i].v;

        if(vis[v])

            continue;

        ans-=cal(v,e[i].w);

        solve(v);

    }

}

int main(){

    while(~scanf("%d%d",&n,&k)&&(n+k)){

        tot=,ans=;

        memset(head,-,sizeof(head));

        memset(vis,,sizeof(vis));

        for(int i=;i<n;i++){

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            addedge(u,v,w);

            addedge(v,u,w);

        }

        solve();

        printf("%lld\n",ans);

    }

    return ;

}

poj1987

题：http://poj.org/problem?id=1987

和上面一样的题意，不一样的写法

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<algorithm>

#include<cmath>

using  namespace std;

const int M=2e5+;

const int inf=0x3f3f3f3f;

typedef long long ll;

char s[];

ll ans;

int num,n,m;

ll sz[M],maxv[M],dis[M],k;

int maxx,vis[M],head[M],reco,total,tot,root;

struct node{

    int v,nextt;

    ll w;

}e[M<<];

void addedge(int u,int v,int w){

    e[tot].v=v;

    e[tot].w=w;

    e[tot].nextt=head[u];

    head[u]=tot++;

}

void addedge(int u,int v){

    e[tot].v=v;

    e[tot].nextt=head[u];

    head[u]=tot++;

}

void dfsroot(int u,int f){

    sz[u]=;

    ll maxson=;

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(v!=f&&!vis[v]){

            dfsroot(v,u);

            sz[u]+=sz[v];

            maxson=max(maxson,sz[v]);

        }

    }

    maxson=max(maxson,total-sz[u]);

    if(maxson<reco)

        root=u,reco=maxson;

}

void dfsdis(int u,int f,ll d){

    dis[num++]=d;

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(v==f||vis[v])

            continue;

        dfsdis(v,u,d+e[i].w);

    }

}

ll cal(int u,int f,ll d){

    ll sum=;

    num=;

    dfsdis(u,f,d);

    sort(dis,dis+num);

    int i=,j=num-;

    while(i<j){

        while(dis[i]+dis[j]>k&&i<j){

            j--;

        }

        sum+=1ll*(j-i);

        i++;

    }

    return sum;

}

void doit(int u,int f){

    ///跨越u的路径和在同一个子树中的路径

    ans+=cal(u,f,);

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

///因为同一个子树中的路径在dfs下去的时候会被算到，所以要减去被预先算过的

        if(v!=f&&!vis[v]){

            ans-=cal(v,u,e[i].w);

        }

    }

}

void solve(int u,int f){

    vis[u]=;

    doit(u,f);

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(v!=f&&!vis[v]){

            total=sz[v];

            reco=inf;

            dfsroot(v,u);

            solve(root,);

        }

    }

}

int main(){

    scanf("%d%d",&n,&m);

    memset(head,-,sizeof(head));

    while(m--){

        int u,v;

        ll w;

        scanf("%d%d%lld%s",&u,&v,&w,s);

        addedge(u,v,w);

        addedge(v,u,w);

    }

    scanf("%lld",&k);

    total=n;

    reco=inf;

    dfsroot(,);

    solve(root,);

    printf("%lld\n",ans);

    return ;

}

题：https://www.luogu.org/problem/P4149

题意：给定固定路径长，边数最少路径

#include<bits/stdc++.h>

using namespace std;

const int M=2e5+;

const int inf=0x3f3f3f3f;

const int N=1e6+;

int vis[M],temp[N],sz[M],head[M];

int n,k,total,reco,root;

int ans,tot;

#define pb push_back

struct node{

    int u,v,w,nextt;

}e[M<<];

void addedge(int u,int v,int w){

    e[tot].v=v;

    e[tot].w=w;

    e[tot].nextt=head[u];

    head[u]=tot++;

}

void dfsroot(int u,int f){

    int maxx=;

    sz[u]=;

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(!vis[v]&&v!=f){

            dfsroot(v,u);

            sz[u]+=sz[v];

            maxx=max(maxx,sz[v]);

        }

    }

    maxx=max(maxx,total-sz[u]);

    if(reco>maxx)

        reco=maxx,root=u;

}

void cal(int u,int f,int d,int num){

    if(d>k)

        return ;

    ans=min(ans,temp[k-d]+num);

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(!vis[v]&&v!=f){

            cal(v,u,d+e[i].w,num+);

        }

    }

}

void update(int u,int f,int d,int num){

    if(d>k)

        return ;

    temp[d]=min(temp[d],num);

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(!vis[v]&&v!=f){

            update(v,u,d+e[i].w,num+);

        }

    }

}

void Clear(int u,int f,int d){

    if(d>=k)

        return ;

    temp[d]=inf;

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(v!=f&&!vis[v]){

            Clear(v,u,d+e[i].w);

        }

    }

}

void dfs1(int u,int f){

    sz[u]=;

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(!vis[v]&&v!=f){

            dfs1(v,u);

        }

    }

}

void doit(int u,int f){

    dfs1(u,f);

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(!vis[v]&&v!=f){

            cal(v,u,e[i].w,);

            update(v,u,e[i].w,);

        }

    }

    Clear(u,f,);

}

void solve(int u,int f){

    vis[u]=;

    temp[]=;

    doit(u,f);

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(!vis[v]&&v!=f){

            total=sz[v];

            reco=inf;

            dfsroot(v,u);

            solve(root,);

        }

    }

}

int main(){

    scanf("%d%d",&n,&k);

    for(int i=;i<=n;i++)

        head[i]=-;

    for(int i=;i<=k;i++)

        temp[i]=inf;

    for(int u,v,w,i=;i<n;i++){

        scanf("%d%d%d",&u,&v,&w);

        u++,v++;

        addedge(u,v,w);

        addedge(v,u,w);

    }

    total=n;

    reco=inf;

    ans=inf;

    dfsroot(,);

    solve(root,);

    if(ans==inf)

        puts("-1");

    else

        printf("%d\n",ans);

    return ;

}

题（求点权处理的题）：http://acm.hdu.edu.cn/showproblem.php?pid=4812

题意：给定一棵 n 个点的树,每个点有权值 Vi，问是否存在一条路径使得路径上所有点的权值乘积 mod(10^6 + 3) 为 K，输出路径的首尾标号,若有多解,输出字典序最小的解

注意：更新就更新以重点为起点的路径，枚举答案时则用以重点孩子为起点的路径

除法，逆元处理

#pragma comment(linker,"/STACK:102400000,102400000")

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<vector>

using namespace std;

#define pb push_back

typedef long long ll;

const int M=1e5+;

const int mod=1e6+;

const int inf=0x3f3f3f3f;

int reco,total,root,n;

ll k;

ll sz[M],a[M],vis[M];

int ansi,ansj;

int temp[mod+];

struct node{

    int v,nextt;

}e[M<<];

int head[M];

int tot;

int inv[mod+];

void addedge(int u,int v){

    e[tot].v=v;

    e[tot].nextt=head[u];

    head[u]=tot++;

}

void iniInv(){

    inv[]=;

    for(int i=;i<mod;i++)

        inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;

}

void dfsroot(int u,int f){

    sz[u]=;

    ll maxson=;

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(v!=f&&!vis[v]){

            dfsroot(v,u);

            sz[u]+=sz[v];

            maxson=max(maxson,sz[v]);

        }

    }

    maxson=max(maxson,total-sz[u]);

    if(maxson<reco)

        root=u,reco=maxson;

}

void up(int x,int y){

    int minn=min(x,y);

    int maxx=max(x,y);

    if(minn<ansi){

        ansi=minn,ansj=maxx;

    }

    else if(minn==ansi){

        if(maxx<ansj)

            ansj=maxx;

    }

}

void cal(int u,int f,int d){

    int x=temp[k*inv[d]%mod];

    if(x)

        up(u,x);

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(!vis[v]&&v!=f){

            cal(v,u,d*a[v]%mod);

        }

    }

}

void update(int u,int f,int d){

    if(!temp[d])

        temp[d]=u;

    else

        temp[d]=min(temp[d],u);

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(!vis[v]&&v!=f){

            update(v,u,d*a[v]%mod);

        }

    }

}

void del(int u,int f,int d){

    temp[d]=;

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(!vis[v]&&v!=f){

            del(v,u,d*a[v]%mod);

        }

    }

}

void doit(int u,int f){

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(!vis[v]){

            cal(v,u,a[v]);

            update(v,u,a[u]*a[v]%mod);

        }

    }

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(!vis[v]){

            del(v,u,a[u]*a[v]%mod);

        }

    }

}

void solve(int u,int f){

    vis[u]=;

    temp[a[u]]=u;

    doit(u,f);

    temp[a[u]]=;

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(!vis[v]&&v!=f){

            reco=inf;

            total=sz[v];

            dfsroot(v,u);

            solve(root,);

        }

    }

}

int main(){

//    freopen("in","r",stdin);

    iniInv();

    while(scanf("%d%lld",&n,&k)!=EOF){

        tot=;

        memset(head,-,sizeof(head));

        for(int i=;i<=n;i++)

            scanf("%d",&a[i]),vis[i]=;

        memset(temp,,sizeof(temp));

        for(int u,v,i=;i<n;i++){

            scanf("%d%d",&u,&v);

            addedge(u,v);

            addedge(v,u);

        }

        ansi=ansj=inf;

        reco=inf;

        total=n;

        dfsroot(,);

        solve(root,);

        if(ansi==inf){

            puts("No solution");

        }

        else{

            printf("%d %d\n",ansi,ansj);

        }

    }

    return ;

}

bzoj 2152

题：https://www.lydsy.com/JudgeOnline/problem.php?id=2152

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

const int M=2e4+;

struct node{

    int v,nextt;

    int w;

}e[M<<];

int head[M],dis[],sz[M],maxv[M],vis[M],n,tot,fenzi,maxx,root;

void addedge(int u,int v,int w){

    e[tot].v=v;

    e[tot].nextt=head[u];

    e[tot].w=w;

    head[u]=tot++;

}

void dfssz(int u,int f){

    maxv[u]=;

    sz[u]=;

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(v==f||vis[v])

            continue;

        dfssz(v,u);

        sz[u]+=sz[v];

        maxv[u]=max(maxv[u],sz[v]);

    }

}

void dfsroot(int r,int u,int f){

    maxv[u]=max(maxv[u],sz[r]-sz[u]);

    if(maxx>maxv[u]){

        maxx=maxv[u];

        root=u;

    }

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(v==f||vis[v])

            continue;

        dfsroot(r,v,u);

    }

}

void dfsdis(int u,int f,int d){

    dis[d%]++;

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(vis[v]||v==f)

            continue;

        dfsdis(v,u,(d+e[i].w)%);

    }

}

ll cal(int u,int d){

    dis[]=dis[]=dis[]=;

    dfsdis(u,-,d);

    ll sum=;

    for(int i=;i<;i++)

        for(int j=;j<;j++)

            if((i+j)%==)

                sum+=dis[i]*dis[j];

    return sum;

}

void solve(int u){

    maxx=n;

    dfssz(u,-);

    dfsroot(u,u,-);

    fenzi+=cal(root,);

    vis[root]=;

    for(int i=head[root];~i;i=e[i].nextt){

        int v=e[i].v;

        if(vis[v])

            continue;

        fenzi-=cal(v,e[i].w);

        solve(v);

    }

}

int main(){

    scanf("%d",&n);

    memset(head,-,sizeof(head));

    for(int i=;i<n;i++){

        int u,v,w;

        scanf("%d%d%d",&u,&v,&w);

        addedge(u,v,w);

        addedge(v,u,w);

    }

    solve();

    int fenmu=n*n;

    //cout<<fenmu<<endl;

    int g=__gcd(fenzi,fenmu);

    printf("%d/%d",fenzi/g,fenmu/g);

    return ;

}

题：https://ac.nowcoder.com/acm/contest/1099/I

题意：找出路径和为2019倍数的路径

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<map>

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

const ll INF=1e18;

ll ans=;

int tot,maxx,root;

const int M=2e4+;

struct node{

    int v,w,nextt;

}e[M<<];

int head[M],vis[M],sz[M],maxv[M],dis[],n;

void addedge(int u,int v,int w){

    e[tot].v=v;

    e[tot].w=w;

    e[tot].nextt=head[u];

    head[u]=tot++;

}

void dfssz(int u,int f){

    sz[u]=;

    maxv[u]=;

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;//cout<<"!!"<<endl;

        if(v==f||vis[v])

            continue;

        dfssz(v,u);

        sz[u]+=sz[v];

        maxv[u]=max(maxv[u],sz[v]);

    }

}

void dfsroot(int r,int u,int f){

    maxv[u]=max(maxv[u],sz[r]-sz[u]);

    if(maxv[u]<maxx){

        maxx=maxv[u];

        root=u;

    }

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(vis[v]||v==f)

            continue;

        dfsroot(r,v,u);

    }

}

void dfsdis(int u,int d,int f){

    dis[d%]++;

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(v==f||vis[v])

            continue;

        dfsdis(v,(d+e[i].w)%,u);

    }

}

ll cal(int u,int d){

    ll sum=;

    for(int i=;i<=;i++)

        dis[i]=;

    dfsdis(u,d,-);

    for(int i=;i<;i++){

        if(dis[i]==||dis[(-i)%]==)

            continue;

        sum+=1ll*dis[i]*(dis[(-i)%]);

    }

   // mp.clear();

    return sum;

}

void solve(int u){

    maxx=n;

    dfssz(u,-);

    dfsroot(u,u,-);

    ans+=cal(root,);

    vis[root]=;

    for(int i=head[root];~i;i=e[i].nextt){

        int v=e[i].v;

        if(vis[v])

            continue;

        ans-=cal(v,e[i].w);

        solve(v);

    }

}

int main(){

    while(~scanf("%d",&n)){

        tot=,ans=0ll;

        memset(head,-,sizeof(head));

        memset(vis,,sizeof(vis));

        for(int i=;i<n;i++){

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            addedge(u,v,w);

            addedge(v,u,w);

        }

        solve();

        printf("%lld\n",(ans-n)/);//要减去自己到自己的贡献

    }

    return ;

}

点分治好题：https://www.luogu.org/problem/P2664

最终思考于：https://blog.csdn.net/wu_tongtong/article/details/78963542

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

const int M=2e5+;

int reco,total;

ll sz[M];

int head[M],C[M],vis[M],cnt[M],maxv[M],n,tot,root,num,sum,tt;

ll ans[M],col[M];

struct node{

    int v,nextt;

}e[M<<];

void addedge(int u,int v){

    e[tot].v=v;

    e[tot].nextt=head[u];

    head[u]=tot++;

}

void dfsroot(int u,int f){

    sz[u]=;

    ll maxson=;

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(v!=f&&!vis[v]){

            dfsroot(v,u);

            sz[u]+=sz[v];

            maxson=max(maxson,sz[v]);

        }

    }

    maxson=max(maxson,total-sz[u]);

    if(maxson<reco)

        root=u,reco=maxson;

}

void dfs1(int u,int f){

    sz[u]=;

    cnt[C[u]]++;

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(v!=f&&!vis[v]){

            dfs1(v,u);

            sz[u]+=sz[v];

        }

    }

    if(cnt[C[u]]==){

        sum+=sz[u];

        col[C[u]]+=sz[u];

    }

    cnt[C[u]]--;

}

void change(int u,int f,int sign){

    cnt[C[u]]++;

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(v!=f&&!vis[v])

            change(v,u,sign);

    }

    if(cnt[C[u]]==){

        sum+=1ll*sign*sz[u];

        col[C[u]]+=1ll*sign*sz[u];

    }

    cnt[C[u]]--;

}

void dfs2(int u,int f){

    cnt[C[u]]++;

    if(cnt[C[u]]==){

        sum-=col[C[u]];

        num++;

    }

    ans[u]+=1ll*sum+num*tt;

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(v!=f&&!vis[v]){

            dfs2(v,u);

        }

    }

    if(cnt[C[u]]==){

        sum+=col[C[u]];

        num--;

    }

    cnt[C[u]]--;

}

void cle(int  u,int f){

    cnt[C[u]]=;

    col[C[u]]=;

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(v!=f&&!vis[v])

            cle(v,u);

    }

}

void doit(int u,int f){

    dfs1(u,f);

    ans[u]+=(ll)sum;

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(v!=f&&!vis[v]){

            cnt[C[u]]++;

            col[C[u]]-=sz[v];

            sum-=sz[v];

            change(v,u,-);

            cnt[C[u]]--;

            tt=sz[u]-sz[v];

            dfs2(v,u);

            cnt[C[u]]++;

            col[C[u]]+=sz[v];

            sum+=sz[v];

            change(v,u,);

            cnt[C[u]]--;

        }

    }

    sum=num=;

    cle(u,f);

}

void solve(int u,int f){

    vis[u]=;

    doit(u,f);

    for(int i=head[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(v!=f&&!vis[v]){

            total=sz[v];

            reco=inf;

            dfsroot(v,u);

            solve(root,);

        }

    }

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        head[i]=-;

    for(int i=;i<=n;i++)

        scanf("%d",&C[i]);

    for(int u,v,i=;i<n;i++){

        scanf("%d%d",&u,&v);

        addedge(u,v);

        addedge(v,u);

    }

    total=n;

    reco=inf;

    dfsroot(,);

    solve(root,);

    for(int i=;i<=n;i++)

        printf("%lld\n",ans[i]);

    return ;

}

巴特西

树分治（挑战p360）

最新文章

热门文章