poj2114树分治

题意:给你一棵树,每条边有权值,求有没有一条链使得权值和为k

题解:和上一题类似,依旧是树分治,只是我们储存结果的时候是判断加起来为k的点对数,刚开始本来想用map存答案,结果就t了,后来用了vector,数组等各种,最后用数组,绝望的把memset改成for就过了。

学到一个新的点:如果我们调用了m[i](m是map),不管m[i]是不是0,当我们遍历map时就会出现这个数,但是second=0

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cassert>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1 using namespace std;
using namespace __gnu_cxx; const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f; struct edge{
int to,Next,c;
}e[maxn];
int cnt,head[N];
int sz[N],zx[N],dis[N];
int k,son[N],sonsz;
bool vis[N];
void add(int u,int v,int c)
{
e[cnt].to=v;
e[cnt].c=c;
e[cnt].Next=head[u];
head[u]=cnt++;
}
void dfssz(int u,int f,int &sum)
{
sum++;
sz[u]=;
for(int i=head[u];~i;i=e[i].Next)
{
int x=e[i].to;
if(x==f||vis[x])continue;
dfssz(x,u,sum);
sz[u]+=sz[x];
}
}
void dfszx(int u,int f,int sum,int &ans,int &id)
{
zx[u]=sum-sz[u];
for(int i=head[u];~i;i=e[i].Next)
{
int x=e[i].to;
if(x==f||vis[x])continue;
dfszx(x,u,sum,ans,id);
zx[u]=max(zx[u],sz[x]);
}
if(ans>zx[u])
{
ans=zx[u];
id=u;
}
}
int findzx(int root)
{
int sum=,ans=inf,id=;
dfssz(root,-,sum);
dfszx(root,-,sum,ans,id);
return id;
}
void dfsdis(int u,int f)
{
son[sonsz++]=dis[u];
for(int i=head[u];~i;i=e[i].Next)
{
int x=e[i].to;
if(x==f||vis[x])continue;
dis[x]=dis[u]+e[i].c;
dfsdis(x,u);
}
}
int ok1()
{
sort(son,son+sonsz);
/* for(int i=0;i<ma.size();i++)cout<<ma[i]<<" ";
cout<<endl;
cout<<"---------"<<endl;*/
int ans=;
for(int i=;i<sonsz;i++)
{
int p1=upper_bound(son,son+sonsz,k-son[i])-son;
int p2=lower_bound(son,son+sonsz,k-son[i])-son;
ans+=p1-p2;
}
return ans/;
}
void dfsson(int u,int f)
{
son[sonsz++]=dis[u];
for(int i=head[u];~i;i=e[i].Next)
{
int x=e[i].to;
if(x==f||vis[x])continue;
dfsson(x,u);
}
}
int solve(int root)
{
int p=findzx(root);
dis[p]=;
sonsz=;
dfsdis(p,-);
int ans=ok1();
for(int i=head[p];~i;i=e[i].Next)
{
int x=e[i].to;
if(vis[x])continue;
sonsz=;
dfsson(x,p);
ans-=ok1();
}
vis[p]=;
for(int i=head[p];~i;i=e[i].Next)
{
int x=e[i].to;
if(vis[x])continue;
ans+=solve(x);
}
return ans;
}
void init()
{
cnt=;
memset(head,-,sizeof head);
}
int main()
{
/* ios::sync_with_stdio(false);
cin.tie(0);*/
int n;
while(scanf("%d",&n),n)
{
init();
for(int i=;i<=n;i++)
{
int a,b;
while(scanf("%d",&a))
{
if(!a)break;
scanf("%d",&b);
add(i,a,b);
add(a,i,b);
}
}
while()
{
for(int i=;i<=n;i++)vis[i]=;
scanf("%d",&k);
if(!k)break;
if(solve()>)puts("AYE");
else puts("NAY");
}
puts(".");
}
return ;
}
/******************* ********************/
上一篇:CSS3 - 鼠标移入移出时改变样式


下一篇:LAMP配置参考地址