[主席树优化建图][网络流] Bzoj P3681 Arietta

r囧r小猫 2021-10-15 07:15 279阅读 0赞

## Description ##

Arietta 的命运与她的妹妹不同,在她的妹妹已经走进学院的时候,她仍然留在山村中。  
但是她从未停止过和恋人 Velding 的书信往来。一天,她准备去探访他。  
对着窗外的阳光,临行前她再次弹起了琴。  
她的琴的发声十分特殊。  
让我们给一个形式化的定义吧。  
所有的 n 个音符形成一棵由音符 C ( 1 号节点) 构成的有根树,每一个音符有一个音高 Hi 。  
Arietta 有 m 个力度,第 i 个力度能弹出 Di 节点的子树中,音高在 \[Li,Ri\] 中的任意一个音符。  
为了乐曲的和谐,Arietta 最多会弹奏第 i 个力度 Ti 次。  
Arietta 想知道她最多能弹出多少个音符。

## Input ##

输入共 m + 3 行。  
第一行两个整数 n, m ,意义如题目所述。  
第二行 n - 1 个整数 Pi ,表示节点 i ( i = 2 . . . n ) 的父亲节点的编号。  
第三行 n 个整数 Hi 。  
接下来的 m 行,每行四个整数 Li,Ri,D,Ti

## Output ##

输出一个整数表示 Arietta 最多能弹奏多少音符。  
数据范围与约定  
对于 100% 的数据,1 ≤ n, m ≤ 10000 。  
对于所有数据,1 ≤ Hi , Ti , Pi ≤ n, 1 ≤ Li ≤ Ri ≤ n 。

## Sample Input ##

5 2  
1 1 2 2  
5 3 2 4 1  
1 3 2 1  
3 5 1 4

## Sample Output ##

## HINT ##

第一个力度弹奏音符5，第二个力度弹奏音符1,2,4。

数据范围与约定  
  
对于 100% 的数据,1 ≤ n, m ≤ 10000 。  
  
对于所有数据1<=Hi,Ti,Pi<=N,1<=Li<=Ri<=N

# 题解 #

*  这显然是一个网络流模型，考虑如何优化建图
 *  暴力做法是对每棵子树都用一棵线段树来优化建图，但时空复杂度显然无法接受
 *  我们考虑用主席树来优化建图，先给每个点单独建立主席树，然后dfs下去，并且将一个点的所有子树合并起来，相当于新建了n棵主席树
 *  因为这样从root\[x\]查询到的区间就可以直接表示满足题意的点了，然后就是最大流了
 *  **1A真的爽死我辽**

# 代码 #

1 #include <cstdio>
     2 #include <iostream>
     3 #include <cstring>
     4 #include <queue>
     5 #include <vector>
     6 #define inf 1000000000
     7 #define N 100010
     8 using namespace std;
     9 int  n,m,s,t,tot,cnt=1,maxflow,head[N*10],cur[N*10],h[N*10],root[N],lson[N*10],rson[N*10];
    10 struct edge{
        int to,from,v;}e[N*10];
    11 vector<int>son[N];
    12 queue<int>Q;
    13 void add(int x,int y,int v)
    14 {
    15     e[++cnt].to=y,e[cnt].from=head[x],head[x]=cnt,e[cnt].v=v;
    16     e[++cnt].to=x,e[cnt].from=head[y],head[y]=cnt,e[cnt].v=0;
    17 }
    18 void insert(int x)
    19 {
    20     int l,r,mid;
    21     for (l=1,r=n,++tot;l<r;tot++)
    22         if (x<=(mid=(l+r>>1))) add(tot,lson[tot]=tot+1,inf),r=mid;
    23         else add(tot,rson[tot]=tot+1,inf),l=mid+1;
    24     add(tot,t,1);
    25 }
    26 int merge(int x,int y,int l,int r)
    27 {
    28     if (x*y==0) return x+y;
    29     int k=++tot,mid=l+r>>1; 
    30     if (l==r) add(k,x,inf),add(k,y,inf);
    31     else add(k,lson[k]=merge(lson[x],lson[y],l,mid),inf),add(k,rson[k]=merge(rson[x],rson[y],mid+1,r),inf);
    32     return k;
    33 }
    34 void dfs(int x)
    35 {
    36     if (!son[x].size()) return;
    37     for (int i=son[x].size()-1;~i;i--) dfs(son[x][i]),root[x]=merge(root[x],root[son[x][i]],1,n);
    38 }
    39 bool bfs()
    40 {
    41     for (int i=0;i<=tot;i++) h[i]=-1;
    42     Q.push(s),h[s]=0;
    43     while (!Q.empty())
    44     {
    45         int x=Q.front();Q.pop();
    46         for (int i=head[x];i;i=e[i].from) if (e[i].v&&h[e[i].to]==-1) h[e[i].to]=h[x]+1,Q.push(e[i].to);
    47     }
    48     return h[t]!=-1;
    49 }
    50 int dfs(int x,int f)
    51 {
    52     if (x==t) return f;
    53     int r,flow=0;
    54     for (int i=cur[x];i;i=e[i].from)
    55         if (e[i].v&&h[e[i].to]==h[x]+1)
    56         {
    57             r=dfs(e[i].to,min(e[i].v,f-flow)),e[i].v-=r,e[i^1].v+=r,flow+=r;
    58             if (e[i].v) cur[x]=i;
    59             if (flow==f)return f;       
    60         }
    61     if (!flow) h[x]=-1;
    62     return flow;
    63 }
    64 void dinic()
    65 {
    66     maxflow=0;
    67     while (bfs()) { for (int i=0;i<=tot;i++) cur[i]=head[i]; maxflow+=dfs(s,inf); }
    68 }
    69 void query(int d,int l,int r,int x,int y)
    70 {
    71     if (!d) return;
    72     if (l==x&&r==y) { add(tot,d,inf); return; }
    73     int mid=l+r>>1;
    74     if (y<=mid) query(lson[d],l,mid,x,y);
    75     else if (x>mid) query(rson[d],mid+1,r,x,y);
    76     else query(lson[d],l,mid,x,mid),query(rson[d],mid+1,r,mid+1,y);
    77 }
    78 int main()
    79 {
    80     scanf("%d%d",&n,&m),s=0,t=tot=1;
    81     for (int i=2,x;i<=n;i++) scanf("%d",&x),son[x].push_back(i);
    82     for (int i=1,x;i<=n;i++) root[i]=tot+1,scanf("%d",&x),insert(x);
    83     dfs(1);
    84     for (int l,r,x,y;m;m--) scanf("%d%d%d%d",&l,&r,&x,&y),add(s,++tot,y),query(root[x],1,n,l,r);
    85     dinic(),printf("%d",maxflow);
    86 }

转载于:https://www.cnblogs.com/Comfortable/p/11182396.html