Lvat_s Blog

的确是好题。。。

根本不会，然后copy了PoPoQQQ大爷的代码

反正就是LCT乱搞

题解

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int Mod=10007,N=30005;

int n,m,vis[N],cnt,fa[N];

struct Line{
int k,b;
Line(){}
Line(int ks,int bs){k=ks;b=bs;}
friend Line operator+(Line A,Line B){return Line(A.k*B.k%Mod,(B.k*A.b+B.b)%Mod);}
int F(int x){return (k*x+b)%Mod;}
};

struct Node{
Line v,sum;
Node *ch[2],*fa,*spc;
Node(int k,int b);
void Pushup();
}*root[N],*Null;

Node::Node(int k,int b){ch[0]=ch[1]=fa=spc=Null;v=sum=Line(k,b);}
void Node::Pushup(){sum=ch[0]->sum+v+ch[1]->sum;}
bool Notroot(Node *x){return x->fa->ch[0]==x || x->fa->ch[1]==x;}
Node *GetNull(){Node *p=new Node(1,0);p->ch[0]=p->ch[1]=p->fa=p;return p;}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x){
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
	if(!Notroot(y))Rotate(x,y->ch[0]==x);
	else {
		if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else {Rotate(y,0);Rotate(x,0);}
	}
}
}

void Access(Node *x){for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;x->Pushup();}}
Node *Findroot(Node *x){Access(x);Splay(x);while(x->ch[0]!=Null)x=x->ch[0];return x;}
pair<int,int>exgcd(int a,int b){if(!b)return make_pair(1,0);pair<int,int>P=exgcd(b,a%b);return make_pair(P.second,P.first-a/b*P.second);}
int Inv(int x){int P=exgcd((x+Mod)%Mod,Mod).first;return (P%Mod+Mod)%Mod;}
void DFS(int u){vis[u]=cnt;if(vis[fa[u]]==cnt){root[u]->spc=root[fa[u]];return;}root[u]->fa=root[fa[u]];if(!vis[fa[u]])DFS(fa[u]);}

int Query(Node *x){
Node *rt=Findroot(x);
Access(rt->spc);
Splay(rt->spc);
int k=rt->spc->sum.k,b=rt->spc->sum.b;
if(k==1 && !(b==0 && x->sum.k==0))return b?-1:-2;
Access(x);
Splay(x);
return x->sum.F((Mod-b)*Inv(k-1)%Mod);
}

void Modify(Node *x,int k,Node *f,int b){
Node *rt=Findroot(x);
x->v.k=k;x->v.b=b;x->Pushup();
if(x==rt)x->spc=Null;
else {
	Access(x);
	Splay(x);
	x->ch[0]->fa=Null;
    x->ch[0]=Null;
    x->Pushup();
    if(Findroot(rt->spc)!=rt){
		Access(rt);
		Splay(rt);
		rt->fa=rt->spc;
		rt->spc=Null;
    }
}
Access(x);
Splay(x);
if(Findroot(f)==x){x->spc=f;}
else x->fa=f;
}

int main(){
freopen("2759.in","r",stdin);
freopen("2759.out","w",stdout);
scanf("%d",&n);
Null=GetNull();
for(int i=1;i<=n;i++){
	int k,f,b;
	scanf("%d %d %d",&k,&f,&b);
    fa[i]=f;
    root[i]=new Node(k,b);
}
for(int i=1;i<=n;i++){if(!vis[i]){cnt++;DFS(i);}}
scanf("%d",&m);
for(int i=1;i<=m;i++){
	char s[10];
	int x,k,p,b;
	scanf("%s",s);
	if(s[0]=='A'){scanf("%d",&x);printf("%d\n",Query(root[x]));}
	if(s[0]=='C'){scanf("%d %d %d %d",&x,&k,&p,&b);Modify(root[x],k,root[p],b);}
}
return 0;
}

旋转卡壳模版题

首先搞出凸包，然后在凸包上面扫描，用两个指针维护单调性

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cstring>
#include<algorithm>
using namespace std;

int n,St_size,St[2005];
double ans;

struct Point{
double x,y;
Point(){}
Point(int sa,int sb){x=sa;y=sb;}
friend Point operator+(Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
friend Point operator-(Point A,Point B){return Point(A.x-B.x,A.y-B.y);}
friend double operator*(Point A,Point B){return A.x*B.y-A.y*B.x;}
friend bool operator<(Point A,Point B){return A.y<B.y || A.y==B.y && A.x<B.x;}
}poi[2005];

double Abs(double x){return x>0?x:-x;}
double Dist(Point A,Point B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}

bool cmp(Point A,Point B){
int Mul=(int)((A-poi[1])*(B-poi[1]));
return (Mul>0)||(Mul==0 && Dist(A,poi[1])<Dist(B,poi[1]));
}

void Graham(){
if(n==1){St[1]=1;St_size=1;return;}
St[1]=1;
St[2]=2;
St_size=2;
for(int i=3;i<=n;i++){
	while(St_size>1 && (poi[St[St_size]]-poi[St[St_size-1]])*(poi[i]-poi[St[St_size-1]])<=0)St_size--;
	St[++St_size]=i;
}
}

void Prepare(){
int pos=1;
for(int i=2;i<=n;i++)if(poi[i]<poi[pos])pos=i;
swap(poi[pos],poi[1]);
sort(poi+2,poi+n+1,cmp);
}

void RC(){
St[St_size+1]=1;
for(int i=1;i<=St_size;i++){
	int poix=i%St_size+1,poiy=(i+2)%St_size+1;
	for(int j=i+2;j<=St_size;j++){
		while(poix%St_size+1!=j && Abs((poi[St[j]]-poi[St[i]])*(poi[St[poix+1]]-poi[St[i]]))>Abs((poi[St[j]]-poi[St[i]])*(poi[St[poix]]-poi[St[i]])))poix=poix%St_size+1;
		while(poiy%St_size+1!=i && Abs((poi[St[poiy+1]]-poi[St[i]])*(poi[St[j]]-poi[St[i]]))>Abs((poi[St[poiy]]-poi[St[i]])*(poi[St[j]]-poi[St[i]])))poiy=poiy%St_size+1;
		ans=max(ans,Abs((poi[St[j]]-poi[St[i]])*(poi[St[poix]]-poi[St[i]]))+Abs((poi[St[poiy]]-poi[St[i]])*(poi[St[j]]-poi[St[i]])));
	}
}
}

int main(){
freopen("1069.in","r",stdin);
freopen("1069.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%lf %lf",&poi[i].x,&poi[i].y);}
Prepare();
Graham();
RC();
printf("%.3lf\n",ans/2);
return 0;
}

双向BFS

怎么写着写着就5kb+了呢……其他人为什么跑得那么快……

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int Smod=9973;
const pair<int,int> tab[]={make_pair(-1,-2),make_pair(-2,-1),make_pair(-1,2),make_pair(-2,1),make_pair(1,-2),make_pair(2,-1),make_pair(1,2),make_pair(2,1)};
const long long Lmod1=233333333333333ll,Lmod2=666666666666667ll;

int T,hn1,hn2,mat[10][10],h1[10005],h2[10005];
char mt[10][10];

struct Hash{
int next,step;
long long L1,L2;
}ha1[1000005],ha2[1000005];

void AddHash1(int s,long long l1,long long l2,int step){
ha1[++hn1].L1=l1;
ha1[hn1].L2=l2;
ha1[hn1].step=step;
ha1[hn1].next=h1[s];
h1[s]=hn1;
}

int FindHash1(int s,long long l1,long long l2){
for(int i=h1[s];i;i=ha1[i].next){
	if(ha1[i].L1==l1 && ha1[i].L2==l2)return i;
}
return 0;
}

void AddHash2(int s,long long l1,long long l2,int step){
ha2[++hn2].L1=l1;
ha2[hn2].L2=l2;
ha2[hn2].step=step;
ha2[hn2].next=h2[s];
h2[s]=hn2;
}

int FindHash2(int s,long long l1,long long l2){
for(int i=h2[s];i;i=ha2[i].next){
	if(ha2[i].L1==l1 && ha2[i].L2==l2)return i;
}
return 0;
}

struct Matrix{
int mt[6][6],now;
friend bool operator==(Matrix A,Matrix B){
for(int i=1;i<=5;i++){
	for(int j=1;j<=5;j++)if(A.mt[i][j]!=B.mt[i][j])return 0;
}
return 1;
}
}Template;

pair<int,pair<long long,long long> > GetHash(Matrix M){
int s=0;
long long l1=0,l2=0;
for(int i=1;i<=5;i++){
	for(int j=1;j<=5;j++){
		s=(s*127+M.mt[i][j])%Smod;
		l1=(l1*233+M.mt[i][j])%Lmod1;
		l2=(l2*667+M.mt[i][j])%Lmod2;
	}
}
return make_pair(s,make_pair(l1,l2));
}

queue<Matrix> Q1,Q2;

void OutMatrix(Matrix M){
puts("This is Mt:");
for(int i=1;i<=5;i++){
	for(int j=1;j<=5;j++){
		printf("%d",M.mt[i][j]);
	}
	putchar('\n');
}
puts("-------------");
}

void BFS(int mode,int st){
if(st>8){puts("-1");return;}
if(mode){
	while(Q1.front().now==st){
		Matrix u=Q1.front();
		//OutMatrix(u);
		Q1.pop();
		int x,y;
		for(x=1;x<=5;x++){for(y=1;y<=5;y++){if(!u.mt[x][y])break;}if(!u.mt[x][y] && y<6)break;}
		//printf("XY:%d %d\n",x,y);
		for(int i=0;i<8;i++){
			int px=x+tab[i].first,py=y+tab[i].second,tc;
			if(px<1 || py<1 || px>5 || py>5)continue;
			swap(u.mt[x][y],u.mt[px][py]);u.now++;
			pair<int,pair<long long,long long> >Pt=GetHash(u);
			tc=FindHash2(Pt.first,Pt.second.first,Pt.second.second);
			if(tc){printf("%d\n",u.now+ha2[tc].step<=15?u.now+ha2[tc].step:-1);return;}
			tc=FindHash1(Pt.first,Pt.second.first,Pt.second.second);
			if(!tc){AddHash1(Pt.first,Pt.second.first,Pt.second.second,u.now);Q1.push(u);}
			swap(u.mt[x][y],u.mt[px][py]);u.now--;
		}
	}
    BFS(mode^1,st);
    return;
}
else {
	while(Q2.front().now==st){
		Matrix u=Q2.front();
		//OutMatrix(u);
		Q2.pop();
		int x,y;
		for(x=1;x<=5;x++){for(y=1;y<=5;y++){if(!u.mt[x][y])break;}if(!u.mt[x][y] && y<6)break;}
		//printf("XY:%d %d\n",x,y);
		for(int i=0;i<8;i++){
			int px=x+tab[i].first,py=y+tab[i].second,tc;
			if(px<1 || py<1 || px>5 || py>5)continue;
			swap(u.mt[x][y],u.mt[px][py]);u.now++;
			pair<int,pair<long long,long long> >Pt=GetHash(u);
			tc=FindHash1(Pt.first,Pt.second.first,Pt.second.second);
			if(tc){printf("%d\n",u.now+ha1[tc].step<=15?u.now+ha1[tc].step:-1);return;}
			tc=FindHash2(Pt.first,Pt.second.first,Pt.second.second);
			if(!tc){AddHash2(Pt.first,Pt.second.first,Pt.second.second,u.now);Q2.push(u);}
			swap(u.mt[x][y],u.mt[px][py]);u.now--;
		}
	}
    BFS(mode^1,st+1);
    return;
}
}

void MakeMt(Matrix &x){
for(int i=1;i<=5;i++){
	for(int j=1;j<=5;j++){
		x.mt[i][j]=mat[i][j];
	}
}
x.now=0;
}

void Prepare(){
mat[1][1]=2;mat[1][2]=2;mat[1][3]=2;mat[1][4]=2;mat[1][5]=2;
mat[2][1]=1;mat[2][2]=2;mat[2][3]=2;mat[2][4]=2;mat[2][5]=2;
mat[3][1]=1;mat[3][2]=1;mat[3][3]=0;mat[3][4]=2;mat[3][5]=2;
mat[4][1]=1;mat[4][2]=1;mat[4][3]=1;mat[4][4]=1;mat[4][5]=2;
mat[5][1]=1;mat[5][2]=1;mat[5][3]=1;mat[5][4]=1;mat[5][5]=1;
}

void First(){
while(!Q1.empty())Q1.pop();
while(!Q2.empty())Q2.pop();
memset(h1,0,sizeof(h1));
memset(h2,0,sizeof(h2));
hn1=0;hn2=0;
}

int main(){
freopen("1085.in","r",stdin);
freopen("1085.out","w",stdout);
scanf("%d",&T);
Prepare();
MakeMt(Template);
while(T--){
	First();
	scanf("%s %s %s %s %s",mt[1]+1,mt[2]+1,mt[3]+1,mt[4]+1,mt[5]+1);
    for(int i=1;i<=5;i++){
		for(int j=1;j<=5;j++){
			if(mt[i][j]=='0')mat[i][j]=1;
			else if(mt[i][j]=='1')mat[i][j]=2;
			else mat[i][j]=0;
		}
    }
    Matrix Tp;
    pair<int,pair<long long,long long> > Pr;
    MakeMt(Tp);
    if(Tp==Template){puts("0");continue;}
    Q1.push(Tp);
    Q2.push(Template);
    Pr=GetHash(Tp);
    AddHash1(Pr.first,Pr.second.first,Pr.second.second,0);
    Pr=GetHash(Template);
    AddHash2(Pr.first,Pr.second.first,Pr.second.second,0);
    BFS(1,0);
}
return 0;
}

这是一个卡内存的悲伤故事

我把UOJ爆了一通才卡完内存，然后又发现在BZOJ上MLE了

然后又是乱卡一通，终于A掉了

题解(PoPoQQQ)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int INF=2100000000,N=900005;

int n,en,S,T,level[N],h[N],cur[N],his[5005],cnt,flow_cnt,ans;
queue<int> Q;

struct Edge{
int b,f,back,next;
}e[N];

void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}

int BFS(){
memset(level,0,sizeof(level));
level[S]=1;
Q.push(S);
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
    for(int i=h[u];i;i=e[i].next){
		int v=e[i].b;
		if(!e[i].f || level[v])continue;
		level[v]=level[u]+1;
		Q.push(v);
    }
}
return level[T];
}

int DFS(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
	int v=e[i].b,fl;
    if(e[i].f && level[v]==level[u]+1 && (fl=DFS(v,min(f,e[i].f)))){
		e[i].f-=fl;
		e[e[i].back].f+=fl;
		f-=fl;
		if(f==0)return flow;
    }
}
return flow-f;
}

int Dinic(){
int ans=0;
while(BFS()){for(int i=1;i<=flow_cnt;i++)cur[i]=h[i];ans+=DFS(S,2100000000);}
return ans;
}

struct SegTree{
int nl,nr,v,pos;
}tree[N];

void Newnode(int &rt,int lastrt){
rt=++cnt;
tree[rt].nl=tree[lastrt].nl;
tree[rt].nr=tree[lastrt].nr;
tree[rt].pos=++flow_cnt;
}

void Update(int &rt,int lastrt,int l,int r,int pos,int val){
Newnode(rt,lastrt);
int mid=l+r>>1;
AddEdge(val,tree[rt].pos,INF);
if(lastrt)AddEdge(tree[lastrt].pos,tree[rt].pos,INF);
if(l==r)return;
if(pos<=mid)Update(tree[rt].nl,tree[lastrt].nl,l,mid,pos,val);
if(pos>mid)Update(tree[rt].nr,tree[lastrt].nr,mid+1,r,pos,val);
}

void Query(int rt,int l,int r,int x,int y,int point){
if(!rt)return;
if(x<=l && r<=y){AddEdge(tree[rt].pos,point,INF);return;}
int mid=l+r>>1;
if(x<=mid)Query(tree[rt].nl,l,mid,x,y,point);
if(y>mid)Query(tree[rt].nr,mid+1,r,x,y,point);
}

int main(){
freopen("3218.in","r",stdin);
freopen("3218.out","w",stdout);
scanf("%d",&n);
S=n*2+1;T=n*2+2;flow_cnt=n*2+2;
for(int i=1;i<=n;i++){
	int a,b,w,l,r,p;
    scanf("%d %d %d %d %d %d",&a,&b,&w,&l,&r,&p);
    ans+=b+w;
    AddEdge(S,i+n,w);AddEdge(i+n,T,b);
    AddEdge(i,i+n,p);
    Update(his[i],his[i-1],0,1000000000,a,i+n);
    Query(his[i-1],0,1000000000,l,r,i);
}
printf("%d\n",ans-Dinic());
return 0;
}

链表启发式合并

每次将元素少的并到多的上面

注意维护一下每个链表维护的真实颜色就好了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1500005;

int n,m,a[N],siz[N],f[N],ans;

struct Line{
int pos;
Line *next;
Line(){}
Line(int x,Line *y){pos=x;next=y;}
}*color[N];

void Add(int x,int pos){Line *tp=new Line(pos,color[x]);color[x]=tp;}

void Merge(int x,int y){
if(x==y)return;
if(siz[f[x]]>siz[f[y]])swap(f[x],f[y]);
x=f[x];y=f[y];
if(!color[x])return;
for(Line *i=color[x];i;i=i->next){if(a[i->pos-1]==y)ans--;if(a[i->pos+1]==y)ans--;}
for(Line *i=color[x];i;i=i->next)a[i->pos]=y;
Line *Tp;
for(Tp=color[x];Tp->next;Tp=Tp->next);
Tp->next=color[y];color[y]=color[x];color[x]=NULL;
siz[y]+=siz[x];siz[x]=0;
}

int main(){
freopen("1483.in","r",stdin);
freopen("1483.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){scanf("%d",&a[i]);f[a[i]]=a[i];siz[a[i]]++;Add(a[i],i);if(a[i]!=a[i-1])ans++;}
for(int i=1;i<=m;i++){
	int opt,x,y;
	scanf("%d",&opt);
	if(opt==1){scanf("%d %d",&x,&y);Merge(x,y);}
	if(opt==2)printf("%d\n",ans);
}
return 0;
}

水并查集

时光倒流就可以了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
 
int f[400005],n,m,k,del[400005],cnt,star[400005],ans[400005];
vector<int> V[400005];
 
int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Union(int x,int y){f[x]=y;}
 
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){int x,y;scanf("%d %d",&x,&y);x++;y++;V[x].push_back(y);V[y].push_back(x);}
scanf("%d",&k);
cnt=n-k;
for(int i=1;i<=k;i++){
    scanf("%d",&star[i]);
    del[++star[i]]=1;
}
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=n;i++){
    if(del[i])continue;
    for(int j=0;j<V[i].size();j++){
        if(!del[V[i][j]] && Find(i)!=Find(V[i][j])){cnt--;Union(Find(i),Find(V[i][j]));}
    }
}
ans[k+1]=cnt;
for(int i=k;i;i--){
    cnt++;del[star[i]]=0;
    for(int j=0;j<V[star[i]].size();j++){if(!del[V[star[i]][j]] && Find(V[star[i]][j])!=Find(star[i]))cnt--,Union(Find(star[i]),Find(V[star[i]][j]));}
    ans[i]=cnt;
}
for(int i=1;i<=k+1;i++)printf("%d\n",ans[i]);
return 0;
}

我做这题的经历告诉了我：不要乱取模

多取了一个mod 然后WA无数次

我这个方法并不是最优的

懒得写题解了

iwtwiioi大爷的题解

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const long long Mod=20101009ll;
int mu[10000005],pri[10000005],cnt,tab[10000005];
long long n,m,ans,s[10000005],Mn;

long long Sum(long long x,long long y){return ((x*(x+1)/2)%Mod)*((y*(y+1)/2)%Mod)%Mod;}

void Prepare(){
mu[1]=1;
Mn=min(n,m);
for(long long i=2;i<=Mn;i++){
	if(!tab[i]){pri[++cnt]=i;mu[i]=-1;}
	for(long long j=1;j<=cnt && i*pri[j]<=Mn;j++){
		tab[i*pri[j]]=1;
		if(i%pri[j]){mu[i*pri[j]]=-mu[i];}
		else {mu[i*pri[j]]=0;break;}
	}
}
for(long long i=1;i<=Mn;i++)s[i]=(s[i-1]+(i*i*mu[i])%Mod)%Mod;
}

long long F(long long x,long long y){
long long j,ans=0,Mn2=min(x,y);
for(long long i=1;i<=Mn2;i=j+1){
	j=min(x/(x/i),y/(y/i));
	ans=(ans+(s[j]-s[i-1])*Sum(x/i,y/i)%Mod)%Mod;
}
return ans;
}

int main(){
freopen("2154.in","r",stdin);
freopen("2154.out","w",stdout);
scanf("%lld %lld",&n,&m);
Prepare();
long long j;
for(long long i=1;i<=Mn;i=j+1){
	j=min(n/(n/i),m/(m/i));
	ans=(ans+(j+i)*(j-i+1)/2%Mod*F(n/i,m/i)%Mod)%Mod;
}
printf("%lld\n",(ans+Mod)%Mod);
return 0;
}

这题是树形DP

暴力枚举三个点的中点

因为每个点的深度在以这个点为根的子树中的深度都一样

所以我们开三个数组维护就可以了

时间复杂度$O(n^2)$

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

int n,en,h[5005],tx1[5005],tx2[5005],dep[5005],mx_dep;
long long ans=0;

struct Edge{
int b,next;
}e[10005];

void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

void Dfs(int u,int fa,int deep){
mx_dep=max(mx_dep,deep);
dep[deep]++;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(v!=fa)Dfs(v,u,deep+1);
}
}

int main(){
freopen("3522.in","r",stdin);
freopen("3522.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;i++){
	int x,y;
	scanf("%d %d",&x,&y);
    AddEdge(x,y);AddEdge(y,x);
}
for(int i=1;i<=n;i++){
	memset(tx1,0,sizeof(tx1));
	memset(tx2,0,sizeof(tx2));
	for(int j=h[i];j;j=e[j].next){
		memset(dep,0,sizeof(dep));
		int v=e[j].b;
		Dfs(v,i,1);
		for(int k=1;k<=mx_dep;k++){
			ans+=tx2[k]*dep[k];
			tx2[k]+=dep[k]*tx1[k];
			tx1[k]+=dep[k];
		}
	}
}
printf("%lld\n",ans);
return 0;
}

因为修改的次数比较少，所以每次暴力重构hash就可以了

LCP可以用二分来做

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;

const unsigned long long Mod1=131ll,Mod2=171ll;

int n,q;
string s;
char ch[1000005];
unsigned long long hash1[1000005],hash2[1000005],Pow1[1000005],Pow2[1000005];

void MakeHash(){
n=s.length();
hash1[n-1]=s[n-1];
hash2[n-1]=s[n-1];
for(int i=n-2;i>=0;i--){
    hash1[i]=hash1[i+1]*Mod1+s[i];
    hash2[i]=hash2[i+1]*Mod2+s[i];
}
}

void Prepare(){
Pow1[0]=1ll;
Pow2[0]=1ll;
for(int i=1;i<=1000000;i++){
    Pow1[i]=Pow1[i-1]*Mod1;
    Pow2[i]=Pow2[i-1]*Mod2;
}
}

pair<unsigned long long,unsigned long long> GetHash(int l,int len){
return make_pair(hash1[l]-hash1[l+len]*Pow1[len],hash2[l]-hash2[l+len]*Pow2[len]);
}

int LCP(int a,int b){
if(a>b)swap(a,b);
int l=0,r=n-b;
while(l<=r){
    int mid=l+r>>1;
    if(GetHash(a,mid)!=GetHash(b,mid))r=mid-1;
    else l=mid+1;
}
return r;
}

int main(){
freopen("2105.in","r",stdin);
freopen("2105.out","w",stdout);
scanf("%d %d",&n,&q);
scanf("%s",ch);s=ch;
Prepare();
MakeHash();
while(q--){
    char opt[10];
    scanf("%s",opt);
    if(opt[0]=='L'){
        int l,r;
        scanf("%d %d",&l,&r);
        l--;r--;
        printf("%d\n",LCP(l,r));
    }
    if(opt[0]=='A'){
        int x;
        scanf("%d %s",&x,ch);
        x--;
        s.insert(x,ch);
        MakeHash();
    }
    if(opt[0]=='C'){
        int x,y;
        scanf("%d %d %s",&x,&y,ch);
        x--;y--;
        for(int i=x;i<=y;i++)s[i]=ch[i-x];
        MakeHash();
    }
    if(opt[0]=='D'){
        int x,y;
        scanf("%d %d",&x,&y);
        x--;y--;
        s.erase(x,y-x+1);
        MakeHash();
    }
}
return 0;
}

这题如果没有环的话就是一个依赖背包问题，可以树形DP

有环就用tarjan缩点就可以了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

int en,en2,h[105],h2[105],w[505],v[105],d[105],low[105],dfn[105],n,m,scc,dp[105][505],cnt,Q[105],Qcnt,inQ[105],belong[105],sv[105],sw[105],in[105];

struct Edge{
int b,next;
}e[10005],e2[10005];

void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

void AddEdge2(int sa,int sb){
in[sb]=1;
e2[++en2].b=sb;
e2[en2].next=h2[sa];
h2[sa]=en2;
}

void Tarjan(int u){
dfn[u]=low[u]=++cnt;
Q[++Qcnt]=u;inQ[u]=1;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(!dfn[v]){Tarjan(v);low[u]=min(low[u],low[v]);}
    else if(inQ[v]){low[u]=min(low[u],dfn[v]);}
}
if(dfn[u]==low[u]){
	scc++;
	int nw=0;
	while(nw!=u){
		nw=Q[Qcnt--];inQ[nw]=0;
		belong[nw]=scc;
		sv[scc]+=v[nw];
		sw[scc]+=w[nw];
	}
}
}

void Rebuild(){
for(int i=1;i<=n;i++){
	for(int j=h[i];j;j=e[j].next){
		int v=e[j].b;
		if(belong[i]!=belong[v]){
			AddEdge2(belong[i],belong[v]);
		}
	}
}
for(int i=1;i<=scc;i++){if(!in[i])AddEdge2(scc+1,i);}
}

void DP(int u){
for(int i=h2[u];i;i=e2[i].next){
	int v=e2[i].b;DP(v);
	for(int j=m-sw[u];j>=0;j--){
		for(int k=0;k<=j;k++){
			dp[u][j]=max(dp[u][j],dp[u][k]+dp[v][j-k]);
		}
	}
}
for(int j=m;j>=0;j--){
	if(j>=sw[u])dp[u][j]=dp[u][j-sw[u]]+sv[u];
	else dp[u][j]=0;
}
}

int main(){
freopen("2427.in","r",stdin);
freopen("2427.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
for(int i=1;i<=n;i++)scanf("%d",&v[i]);
for(int i=1;i<=n;i++){
	scanf("%d",&d[i]);
	if(d[i])AddEdge(d[i],i);
}
for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);
Rebuild();
DP(scc+1);
printf("%d\n",dp[scc+1][m]);
return 0;
}