【给自己的小练习3-点分治】

https://vjudge.net/contest/161666

难点都在于如何处理出答案已经减掉重复的。

题意：给一个树，路径带权，问两个点距离小于等于给定数k有多少对。

点分治的基础题，算答案的时候因为是单调的所以两头走，

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define dow(i,l,r) for(int i=r;i>=l;i--)
#define repedge(i,x) for(int i=fi[x];i;i=e[i].next)
#define maxn 20020
#define maxm 200010
using namespace std;

typedef struct {
    int v,next,toward;
}E;
E e[maxm];
int d[maxn],fi[maxn],size[maxn],msize[maxn],vis[maxn],n,tot,total,m,ans;

void addedge(int j,int k,int l)
{
    e[++total].toward=k;
    e[total].next=fi[j];
    fi[j]=total;
    e[total].v=l;
}

void dfs_len(int x,int fa,int len)
{
    d[++tot]=len;
    repedge(i,x) {
        int too=e[i].toward;
        if (!vis[too] && too!=fa) 
            dfs_len(too,x,len+e[i].v);
    }
}

void dfs_size(int x,int fa)
{
    size[x]=1;
    repedge(i,x) {
        int too=e[i].toward;
        if (!vis[too] && too!=fa) {
            dfs_size(too,x);
            size[x]+=size[too];
        }
    }
}

int dfs_root(int x,int fa,int y)
{
    int r1=0;
    msize[x]=y-size[x];
    repedge(i,x) {
        int too=e[i].toward;
        if (!vis[too] && too!=fa) {
            msize[x]=max(msize[x],size[too]);
            int r2=dfs_root(too,x,y);
            if (!r1 || msize[r2]<msize[r1]) r1=r2;
        }
    }
    if (!r1 || msize[r1]>msize[x]) r1=x;
    return r1;
}

int more(int x,int len)
{
    tot=0;
    dfs_len(x,0,len);
    sort(d+1,d+1+tot);
    int l=0,r=tot,sum=0;
    while (++l<r) {
        while (d[l]+d[r]>m && l<r) r--;
        sum+=r-l;
    }
    return sum;
}

void calc(int x)
{
    int root;
    dfs_size(x,0);
    root=dfs_root(x,0,size[x]);
    ans+=more(root,0);
    vis[root]=1;
    repedge(i,root) {
        int too=e[i].toward;
        if (!vis[too]) {
            ans-=more(too,e[i].v);
            calc(too);
        }
    }
}

int main()
{
    while (~scanf("%d %d",&n,&m)) {
        if (!n) break; 
        memset(vis,0,sizeof(vis));
        memset(fi,0,sizeof(fi));
        total=0;
        rep(i,1,n-1) {
            int j,k,l;
            scanf("%d %d %d",&j,&k,&l);
            addedge(j,k,l);
            addedge(k,j,l);
        }
        ans=0;
        calc(1);
        printf("%d
",ans);
    }
    return 0;
}

View Code

当然现在可以用动态写，多个log

CodeForces - 161D

题意：给一个树，路径带权，问两个点距离恰等于给定数k有多少对。

每次处理出距离数组，注意就是k为偶数的时候答案要改一下下。

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define dow(i,l,r) for(int i=r;i>=l;i--)
#define repedge(i,x) for(int i=fi[x];i;i=e[i].next)
#define maxn 100100
#define maxm 200100
#define LL long long
using namespace std;

typedef struct {
    int toward,next;
}E;
E e[maxm];
int fi[maxn],d[maxn],size[maxn],msize[maxn],vis[maxn],num[505],n,total,m,tot;
LL ans;

void addedge(int j,int k)
{
    e[++total].toward=k;
    e[total].next=fi[j];
    fi[j]=total;
}

void dfs_size(int x,int fa)
{
//    printf("%d %d
",x,fa);
    size[x]=1;
    repedge(i,x) {
        int too=e[i].toward;
        if (!vis[too] && too!=fa) {
            dfs_size(too,x);
            size[x]+=size[too];
        }
    }
} 

int dfs_root(int x,int fa,int y)
{
    int r1=0,r2;
    msize[x]=y-size[x];
    repedge(i,x) {
        int too=e[i].toward;
        if (!vis[too] && too!=fa) {
            msize[x]=max(msize[x],size[too]);
            r2=dfs_root(too,x,y);
            if (msize[r1]>msize[r2]) r1=r2;
        }
    }
    if (msize[r1]>msize[x]) r1=x;
    return r1;
}

void dfs_len(int x,int fa,int len)
{
    if (len>m) return;
    num[len]++;
    repedge(i,x) {
        int too=e[i].toward;
        if (!vis[too] && too!=fa) 
            dfs_len(too,x,len+1);
    }
}

LL more(int x,int len)
{
    memset(num,0,sizeof(num));
    dfs_len(x,0,len);
//    printf("
");
//    rep(i,1,tot) printf("%d ",d[i]);printf("
");
    LL sum=0;
    rep(i,0,m/2) sum+=(LL)num[m-i]*num[i];
    if (m%2==0) 
        sum=sum-(LL)num[m/2]*num[m/2]+(LL)num[m/2]*(num[m/2]-1)/2;
    return sum;
}

void calc(int x)
{
//    printf("%d
",x);
    int root=0;
    dfs_size(x,0);
    root=dfs_root(x,0,size[x]);
//    printf("%d:
	%d",root,ans);
    ans+=more(root,0);
//    printf(" %d
",ans);
    vis[root]=1;
    repedge(i,root) {
        int too=e[i].toward;
        if (!vis[too]) {
    //        printf("	%d:%d ",too,ans);
            ans-=more(too,1);
    //        printf("%d
",ans);
            calc(too);
        }
    } 
}

int main()
{
    scanf("%d %d",&n,&m);
    memset(vis,0,sizeof(vis));
    memset(fi,0,sizeof(fi));
    total=0;
    rep(i,1,n-1) {
        int j,k;
        scanf("%d %d",&j,&k);
        addedge(j,k);
        addedge(k,j);
    } 
    msize[0]=n;
    ans=0;
    calc(1);
    printf("%lld
",ans);
    return 0;
}

View Code

HDU - 4812

题意：题意：给出一棵树，找一条路径，使得路径上的点相乘mod10^6+3等于k，输出路径的两个端点，字典序最小。

点分治不希望处理信息重复怎么做，就是把每个子树分开嘛，最后再递归算子树，

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map> 
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define dow(i,l,r) for(int i=r;i>=l;i--)
#define repedge(i,x) for(int i=fi[x];i;i=e[i].next)
#define maxn 100100
#define LL long long 
#define mm 1000003
using namespace std;

typedef struct{
    int toward,next;
}E;
E e[maxn*2];
typedef struct{
    LL id;
    int x;
}node;
vector<node> now;
vector<int> add;

int sz[maxn],msz[maxn],vis[maxn],fi[maxn],pp[mm],n,ans1,ans2,total,root;
LL num[maxn],inv[mm],m;

void addedge(int j,int k)
{
    ++total;
    e[total].toward=k;
    e[total].next=fi[j];
    fi[j]=total;
}

void dfs_size(int x,int fa)
{
    sz[x]=1;
    repedge(i,x) {
        int too=e[i].toward;
        if (too!=fa && !vis[too]) {
            dfs_size(too,x);
            sz[x]+=sz[too];
        }
    }
}

void dfs_find(int x,int fa,int y)
{
    msz[x]=y-sz[x];
    repedge(i,x) {
        int too=e[i].toward;
        if (!vis[too] && too!=fa) {
            msz[x]=max(msz[x],sz[too]);
            dfs_find(too,x,y);
        }
    }
    if (msz[root]>msz[x]) root=x;
}

void more(int x,int fa,LL len,LL y)
{
//    printf("%d %d %lld %lld
",x,fa,len,y);
//    printf("%lld
",m*inv[len]%mm);
    if (pp[m*inv[len]%mm]) {
        int now1=pp[m*inv[len]%mm],now2=x;
        if (now1>now2) swap(now1,now2);
        if (now1<ans1 || (now1==ans1 && now2<ans2)) ans1=now1,ans2=now2;
    }
    node ll;
    ll.id=len*y%mm,ll.x=x;
    now.push_back(ll);
    repedge(i,x) {
        int too=e[i].toward;
        if (too!=fa && !vis[too]) more(too,x,len*num[too]%mm,y);
    }
}

void calc(int x)
{
    dfs_size(x,0);
    root=0;
    dfs_find(x,0,sz[x]);
    add.push_back(num[root]);
    pp[num[root]]=root;
    vis[root]=1;
//    printf("%d
",root);
    repedge(i,root) {
        int too=e[i].toward;
        if (!vis[too]) {
            now.clear();
            more(too,0,num[too],num[root]);
            rep(i,0,now.size()-1) {
                int j=now[i].id,k=now[i].x;
        //        printf("	%d %d
",j,k);
                if (pp[j]) pp[j]=min(pp[j],k);
                else {
                    pp[j]=k;
                    add.push_back(j);
                }
            }
        }
    }
//    printf("!
");
    rep(i,0,add.size()-1) pp[add[i]]=0;
    add.clear();
//    printf("!!
");
    repedge(i,root) {
        int too=e[i].toward;
        if (!vis[too]) calc(too);
    }
}

int main()
{
    inv[1]=1;
    rep(i,2,mm-1) inv[i]=mm-(mm/i)*inv[mm%i]%mm; 
    while (~scanf("%d %lld",&n,&m)) {
        memset(fi,0,sizeof(fi));
        memset(vis,0,sizeof(vis));
        total=0;
        msz[0]=n;
        rep(i,1,n) scanf("%lld",num+i);
        rep(i,1,n-1) {
            int j,k;
            scanf("%d %d",&j,&k);
            addedge(j,k);
            addedge(k,j);
        }
        ans1=n+1,ans2=n+1; 
        calc(1);
        if (ans1>ans2) swap(ans1,ans2);
        if (ans1<=n) printf("%d %d
",ans1,ans2);
        else printf("No solution
");
    }
    return 0;
}

View Code