树 bzoj2783 JLOI2012

题目大意：给定一棵n个点的树。求满足条件的路径条数。说一个路径是满足条件的，当且仅当这条路径上每个节点深度依次递增且点权和为S。

注释：$1\le n\le 10^5$，$1\le S,val_i\le 10^3$。

---

想法：翻lijinnn的blog翻到的水题。

我们直接遍历整棵树，遍历的时候维护全局桶。然后在回溯的时候将这个点对应的dis删除。这样遍历到每个点时桶内对应的就是这个点到根节点的dis桶，直接统计答案即可。

最后，附上丑陋的代码... ...

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define N 100010using namespace std;multiset
          
           s;bool v[N];int to[N],nxt[N],head[N];int w[N];int tot,sum;int root;int ans=0;inline char nc(){ static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}int read(){ int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+c-'0',c=nc(); return x;}inline void add(int x,int y){ to[++tot]=y; nxt[tot]=head[x]; head[x]=tot;}void dfs(int x,int pre,int data){ s.insert(data); int tmp=data+w[x]; ans+=s.count(tmp-sum); for(int i=head[x];i;i=nxt[i]) dfs(to[i],x,tmp); s.erase(data);}int main(){ int n=read(); sum=read(); for(int i=1;i<=n;i++) w[i]=read(); for(int x,y,i=1;i
          
         
        
       
      
     

小结：裙子的简单数据结构的例题。