题目概述

一棵 $n$ 个节点带点权的树，有 $m$ 种取节点的方法，第 $i$ 种 $[L,R,D,T]$ 表示只能取点权在 $[L,R]$ ，$D$ 子树中的点且只能取 $T$ 次。一个点不能被多次取，问最多能取到多少点（题目里没有说清楚能不能重复取，有毒）。

解题报告

我没事做这种题目遭罪干嘛……题目看错不知道在查些什么。

不能多次取，乱七八糟的限制，分配问题，所以考虑网络流。但建图时会发现很大的问题：边太多了。因为是区间所以可以用线段树优化建图，然后又发现很大的问题：每个节点都要建出线段树。那么肯定考虑主席树，但是主席树并没有合并操作，怎么办呢？学习姿势：用Dsu on tree来建主席树，这样就可以两个 $log$ 。

示例程序

并没有估计过空间开多大，程序里是乱开的。

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10000,maxm=10000,maxt=1500000,maxe=2500000;

int n,m,w[maxn+5],si[maxn+5],SH[maxn+5];vector<int> v[maxn+5];
int E,lnk[maxt+5],cur[maxt+5],son[maxe+5],nxt[maxe+5],e[maxe+5];
int len,ro[maxn+5],ls[maxt+5],rs[maxt+5];int S,T,que[maxt+5],ti,vis[maxt+5],dis[maxt+5];

inline void Add(int x,int y,int z){
    e[E]=z;son[E]=y;nxt[E]=lnk[x];lnk[x]=E++;
    e[E]=0;son[E]=x;nxt[E]=lnk[y];lnk[y]=E++;
}
int Insert(int p,int pos,int ID,int l=1,int r=n){
    int now=++len;if (p) Add(now+n+m,p+n+m,2e9);ls[now]=ls[p];rs[now]=rs[p];if (l==r) return Add(now+n+m,ID,2e9),now;
    int mid=l+(r-l>>1);if (pos<=mid) ls[now]=Insert(ls[p],pos,ID,l,mid); else rs[now]=Insert(rs[p],pos,ID,mid+1,r);return now;
}
void Join(int ID,int p,int L,int R,int l=1,int r=n){
    if (L==l&&r==R) return Add(ID,p+n+m,2e9);int mid=l+(r-l>>1);
    if (R<=mid) Join(ID,ls[p],L,R,l,mid); else if (L>mid) Join(ID,rs[p],L,R,mid+1,r);
    else Join(ID,ls[p],L,mid,l,mid),Join(ID,rs[p],mid+1,R,mid+1,r);
}
void getSH(int x){
    for (int j=(si[x]=1,0),s=v[x].size();j<s;j++)
        getSH(v[x][j]),si[SH[x]]<si[v[x][j]]?SH[x]=v[x][j]:0,si[x]+=si[v[x][j]];
}
void Merge(int x,int p) {ro[p]=Insert(ro[p],w[x],x);for (int j=0,s=v[x].size();j<s;j++) Merge(v[x][j],p);}
void Dfs(int x){
    for (int j=0,s=v[x].size();j<s;j++) Dfs(v[x][j]);if (SH[x]) ro[x]=ro[SH[x]]; else ro[x]=0;
    ro[x]=Insert(ro[x],w[x],x);for (int j=0,s=v[x].size();j<s;j++) if (v[x][j]!=SH[x]) Merge(v[x][j],x);
}
inline bool Bfs(int s,int t){
    int Head=0,Tail=0;que[++Tail]=s;vis[s]=++ti;dis[s]=0;
    while (Head!=Tail)
        for (int x=que[++Head],j=lnk[x],u;~j;j=nxt[j])
            if (vis[u=son[j]]<ti&&e[j]) que[++Tail]=u,vis[u]=ti,dis[u]=dis[x]+1;return vis[t]==ti;
}
int Dfs(int x,int t,int MIN=2e9){
    if (x==t||!MIN) return MIN;int f=0,now;
    for (int &j=cur[x];~j;j=nxt[j])
        if (dis[x]+1==dis[son[j]]&&(now=Dfs(son[j],t,min(MIN,e[j]))))
            {e[j]-=now;e[j^1]+=now;f+=now;if (!(MIN-=now)) break;}return f;
}
inline int Dinic(int s,int t) {int MAX=0;while (Bfs(s,t)) memcpy(cur,lnk,sizeof(lnk)),MAX+=Dfs(s,t);return MAX;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);for (int i=2,fa;i<=n;i++) scanf("%d",&fa),v[fa].push_back(i);
    for (int i=1;i<=n;i++) scanf("%d",&w[i]);memset(lnk,255,sizeof(lnk));getSH(1);Dfs(1);
    for (int i=1;i<=len;i++) {if (ls[i]) Add(i+n+m,ls[i]+n+m,2e9);if (rs[i]) Add(i+n+m,rs[i]+n+m,2e9);};
    for (int i=1,L,R,x,y;i<=m;i++) scanf("%d%d%d%d",&L,&R,&x,&y),Add(S,i+n,y),Join(i+n,ro[x],L,R);
    T=n+m+len+1;for (int i=1;i<=n;i++) Add(i,T,1);return printf("%d\n",Dinic(S,T)),0;
}