【poj1741&1987】

2015.03.16 18:41 Mon | 4次阅读 | 旧日oi | 固定链接 | 源码

树的点分治裸题,今天考试三道都是树上乱搞,基本啥也不会……赶紧补一补

我的程序

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100005
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,k,num,ans,minn,root;
struct edge{
    int to;
    int next;
    int val;
}e[maxn<<1];
int h[maxn],tp;
int dis[maxn],vis[maxn],siz[maxn],mx[maxn];
void ae(int u,int v,int w)
{
    e[tp].to=v;
    e[tp].val=w;
    e[tp].next=h[u];
    h[u]=tp++;
}
void dfssize(int u,int f)
{
    siz[u]=1;mx[u]=0;
    for(int v,i=h[u];i!=-1;i=e[i].next)
    {
        v=e[i].to;
        if(!vis[v]&&v!=f)
        {
            dfssize(v,u);
            siz[u]+=siz[v];
            if(mx[u]<siz[v]) mx[u]=siz[v];
        }
    }
}
void dfsroot(int r,int u,int f)
{
    if(siz[r]-siz[u]>mx[u]) mx[u]=siz[r]-siz[u];
    if(mx[u]<minn) minn=mx[u],root=u;
    for(int v,i=h[u];i!=-1;i=e[i].next)
    {
        v=e[i].to;
        if(v!=f&&!vis[v])
        dfsroot(r,v,u);
    }
}
void dfsdis(int u,int d,int f)
{
    dis[++num]=d;
    for(int v,i=h[u];i!=-1;i=e[i].next)
    {
        v=e[i].to;
        if(!vis[v]&&v!=f)
        dfsdis(v,d+e[i].val,u);
    }
}
int calc(int u,int d)
{
    int ret=0;num=0;
    dfsdis(u,d,0);
    sort(dis+1,dis+num+1);
    int i=1,j=num;
    while(i<j)
    {
        while(dis[i]+dis[j]>k&&i<j) j--;
        ret+=j-i;
        i++;
    }
    return ret;
}
void dfs(int u)
{
    minn=n+1;
    dfssize(u,0);
    dfsroot(u,u,0);
    vis[root]=1;
    ans+=calc(root,0);
    for(int v,i=h[root];i!=-1;i=e[i].next)
    {
        v=e[i].to;
        if(!vis[v])
        {
            ans-=calc(v,e[i].val);
            dfs(v);
        }
    }
}
int main()
{
    n=read();m=read();
    memset(h,-1,sizeof(h));
    int u,v,w;
    for(int i=1;i<=m;i++)
    {
        u=read();v=read();w=read();scanf("%*s");
        ae(u,v,w);ae(v,u,w);
    }
    k=read();
    dfs(1);
    printf("%d\n",ans);
    return 0;
}```