POJ 1741 Tree

正文索引 [隐藏]

题解
代码

题解

点分治
每次寻找树的重心，然后统计经过这颗重心的答案。然后将重心从这个树里去掉，然后分别统计现存的森林里的每颗树的答案。

代码

//while(true) RP++;
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int Maxn=10010;
int n,K;
int Ans;
struct Edge{
    int v,nxt;
    int len;
    Edge(){}
    Edge(int v0,int n0,int l0){
        v=v0;
        nxt=n0;
        len=l0;
    }
};
int head[Maxn+5];
Edge e[Maxn*2+5];
int nume;
inline void addEdge(int u,int v,int len){
    e[++nume]=Edge(v,head[u],len);
    head[u]=nume;
    e[++nume]=Edge(u,head[v],len);
    head[v]=nume;
}
bool vis[Maxn+5];
int siz[Maxn+5],maxSiz[Maxn+5];
void dfsSize(int x,int fa){
    siz[x]=1;
    maxSiz[x]=0;
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].v;
        if (v==fa || vis[v]) continue;
        dfsSize(v,x);
        siz[x]+=siz[v];
        if (siz[v]>maxSiz[x]) maxSiz[x]=siz[v];
    }
}
int Root;
void dfsRoot(int rt,int x,int fa){
    if (siz[rt]-siz[x]>maxSiz[x]) maxSiz[x]=siz[rt]-siz[x];
    if (Root==0 || maxSiz[x]<maxSiz[Root]) Root=x;
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].v;
        if (v==fa || vis[v]) continue;
        dfsRoot(rt,v,x);
    }
}
int dis[Maxn+5];
int tot;
void dfsDist(int x,int ratDist,int fa){
    //printf("To #%d Len=%d\n",x,ratDist);
    dis[++tot]=ratDist;
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].v;
        if (v==fa || vis[v]) continue;
        //printf("%d -> %d Len=%d\n",x,v,e[i].len);
        dfsDist(v,ratDist+e[i].len,x);
    }
}
int getAns(int x,int ratDist){
    int ret=0;
    tot=0;
    dfsDist(x,ratDist,0);
    sort(dis+1,dis+tot+1);
    //for (int i=1;i<=tot;i++) printf("%d ",dis[i]);
    //printf("\n");
    int left=1,right=tot;
    while(left<right){
        while(dis[left]+dis[right]>K && left<right) right--;
        ret+=right-left;
        left++;
    }
    return ret;
}
void DACTree(int x){
    Root=0;
    dfsSize(x,0);
    dfsRoot(x,x,0);
    Ans+=getAns(Root,0);
    vis[Root]=true;
    //printf("Root:%d\n",Root);
    //printf("Add Ans %d\n",getAns(Root,0));
    for (int i=head[Root];i;i=e[i].nxt){
        int v=e[i].v;
        if (vis[v]) continue;
        Ans-=getAns(v,e[i].len);
        //printf("Minus Ans %d\n",getAns(v,e[i].len));
        DACTree(v);
    }
}
inline void solve(){
    if (n==0 || K==0) return;
    memset(vis,false,sizeof(vis));
    memset(head,0,sizeof(head));
    Ans=nume=0;
    for (int i=1;i<n;i++){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        addEdge(x,y,w);
    }
    DACTree(1);
    printf("%d\n",Ans);
}
int main(){
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&K)!=EOF)
        solve();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

//while(true) RP++;

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define LL long long

using namespace std;

const int Maxn=10010;

int n,K;

int Ans;

struct Edge{

int v,nxt;

int len;

Edge(){}

Edge(int v0,int n0,int l0){

v=v0;

nxt=n0;

len=l0;

}

};

int head[Maxn+5];

Edge e[Maxn*2+5];

int nume;

inline void addEdge(int u,int v,int len){

e[++nume]=Edge(v,head[u],len);

head[u]=nume;

e[++nume]=Edge(u,head[v],len);

head[v]=nume;

}

bool vis[Maxn+5];

int siz[Maxn+5],maxSiz[Maxn+5];

void dfsSize(int x,int fa){

siz[x]=1;

maxSiz[x]=0;

for (int i=head[x];i;i=e[i].nxt){

int v=e[i].v;

if (v==fa || vis[v]) continue;

dfsSize(v,x);

siz[x]+=siz[v];

if (siz[v]>maxSiz[x]) maxSiz[x]=siz[v];

}

int Root;

void dfsRoot(int rt,int x,int fa){

if (siz[rt]-siz[x]>maxSiz[x]) maxSiz[x]=siz[rt]-siz[x];

if (Root==0 || maxSiz[x]<maxSiz[Root]) Root=x;

for (int i=head[x];i;i=e[i].nxt){

int v=e[i].v;

if (v==fa || vis[v]) continue;

dfsRoot(rt,v,x);

}

int dis[Maxn+5];

int tot;

void dfsDist(int x,int ratDist,int fa){

//printf("To #%d Len=%d\n",x,ratDist);

dis[++tot]=ratDist;

for (int i=head[x];i;i=e[i].nxt){

int v=e[i].v;

if (v==fa || vis[v]) continue;

//printf("%d -> %d Len=%d\n",x,v,e[i].len);

dfsDist(v,ratDist+e[i].len,x);

}

int getAns(int x,int ratDist){

int ret=0;

tot=0;

dfsDist(x,ratDist,0);

sort(dis+1,dis+tot+1);

//for (int i=1;i<=tot;i++) printf("%d ",dis[i]);

//printf("\n");

int left=1,right=tot;

while(left<right){

while(dis[left]+dis[right]>K && left<right) right--;

ret+=right-left;

left++;

}

return ret;

}

void DACTree(int x){

Root=0;

dfsSize(x,0);

dfsRoot(x,x,0);

Ans+=getAns(Root,0);

vis[Root]=true;

//printf("Root:%d\n",Root);

//printf("Add Ans %d\n",getAns(Root,0));

for (int i=head[Root];i;i=e[i].nxt){

int v=e[i].v;

if (vis[v]) continue;

Ans-=getAns(v,e[i].len);

//printf("Minus Ans %d\n",getAns(v,e[i].len));

DACTree(v);

}

inline void solve(){

if (n==0 || K==0) return;

memset(vis,false,sizeof(vis));

memset(head,0,sizeof(head));

Ans=nume=0;

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

int x,y,w;

scanf("%d%d%d",&x,&y,&w);

addEdge(x,y,w);

}

DACTree(1);

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

}

int main(){

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

while(scanf("%d%d",&n,&K)!=EOF)

solve();

return 0;

}

点分治

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑

POJ 1741 Tree

题解

代码

扫一扫支付

评论放弃治疗

创作日历

文章

标签云

最近访客

POJ 1741 Tree

题解

代码

扫一扫支付

评论 放弃治疗

评论放弃治疗