BZOJ2783: [JLOI2012]树【dfs+set】

dzy posted @ 2013年6月13日 16:50 in BZOJ with tags BZOJ dfs 手工栈 set , 1463 阅读






using namespace std;
const int maxn=200005;
int n,K,vis[maxn]={0},w[maxn],h[maxn],st[maxn],d[maxn],p[maxn],n1[maxn],tot=0;
set<int>S; char buf[5000000],*pt=buf;
inline int getint(){    int r=0;while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline void ae(int a,int b){
    p[tot]=b; n1[tot]=h[a]; h[a]=tot++;
    p[tot]=a; n1[tot]=h[b]; h[b]=tot++;
}int main(){
    fread(pt,1,5000000,stdin); n=getint(); K=getint();
    memset(h,-1,sizeof(h)); S.clear(); S.insert(0);
    for(int i=1;i<=n;i++) w[i]=getint(); int u,v,An=0;
    for(int i=1;i<n;i++) u=getint(),v=getint(),ae(u,v);
    int top=0; st[++top]=1; S.insert(w[1]); d[1]=w[1]; vis[1]=1;
        int o=st[top],flag=0;
        for(int i=h[o];~i;i=n1[i]) if(!vis[p[i]]){
            st[++top]=p[i]; h[o]=n1[i]; d[p[i]]=d[o]+w[p[i]];
            vis[p[i]]=flag=1; S.insert(d[p[i]]);
            if(S.find(d[p[i]]-K)!=S.end()) An++;break;
        }if(!flag){ top--; S.erase(d[o]);}
    }printf("%d\n",An); return 0;
Avatar_small 说:
2023年6月09日 17:07

All the Users of the BoardModelPapers can use those sample papers or Previous Paper Pdf of class-wise study material and blueprint and any for reference purpose only and we are providing the pdf based on internet search according to past years old examination test and those question bank or study material download and shared based on the internet only.

登录 *

loading captcha image...
or Ctrl+Enter