寺中言 @ 2021-12-09 20:46:01
调了三天了，还是没出来，用欧拉序写的，测试点都是在几百行几千行错了，只A了#1#9，求各位巨佬救救蒟蒻QAQ
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline void read(int &x){
x=0;
int y=1;
char a;
a=getchar();
while(a<'0'||a>'9'){
if(a=='-')y=-1;
a=getchar();
}
while(a>='0'&&a<='9'){
x=x*10+a-'0';
a=getchar();
}
x*=y;
}
int n,m,q;
int fv[100008],fw[100008];
vector<int>ff[100008];
int dfn[200008],fst[100008],fed[100008];
int qfz,fzf;
void dfsq(int x,int fa){
++qfz;
dfn[qfz]=x;
fst[x]=qfz;
for(int i=0;i<ff[x].size();++i){
int y=ff[x][i];
if(y==fa)continue;
dfsq(y,x);
}
++qfz;
dfn[qfz]=x;
fed[x]=qfz;
}
int fdp[100008][21],fd[100008];
void dfsq1(int x,int fa){
fdp[x][0]=fa;fd[x]=fd[fa]+1;
for(int i=1;i<=20;++i){
fdp[x][i]=fdp[fdp[x][i-1]][i-1];
}
for(int i=0;i<ff[x].size();++i){
int y=ff[x][i];
if(y==fa)continue;
dfsq1(y,x);
}
}
int lca(int x,int y){
if(fd[x]<fd[y])swap(x,y);
for(int i=20;i>=0;--i){
if(fd[fdp[x][i]]>=fd[y])x=fdp[x][i];
}
if(x==y)return x;
for(int i=19;i>=0;--i){
if(fdp[x][i]!=fdp[y][i])x=fdp[x][i],y=fdp[y][i];
}
return fdp[x][0];
}
int fc[100008];
int fzn;
struct ffff{
int x,y;
int l,r,k;
int num;
bool operator <(const ffff &x)const{
if(l/fzn==x.l/fzn&&r/fzn==x.r/fzn)return k<x.k;
if(l/fzn==x.l/fzn)return r/fzn<x.r/fzn;
return l/fzn<x.l/fzn;
}
}f[100008];
struct fffz{
int x,y;
}fz[100008];
int fzans[100008];
int cqfz[100008];
long long fans[100008];
signed main(){
read(n);read(m);read(q);
n*=2;fzn=pow(n,0.666);n/=2;
for(int i=1;i<=m;++i)read(fv[i]);
for(int i=1;i<=n;++i)read(fw[i]);
for(int i=1;i<n;++i){
int a,b;read(a);read(b);
ff[a].push_back(b);
ff[b].push_back(a);
}
dfsq(1,0);
dfsq1(1,0);
for(int i=1;i<=n;++i)read(fc[i]);
qfz=0;
for(int i=1;i<=q;++i){
int ty;read(ty);
if(ty==0){
++qfz;
read(fz[qfz].x);read(fz[qfz].y);
}
if(ty==1){
++fzf;
int l,r;read(l);read(r);
f[fzf].x=l,f[fzf].y=r;
f[fzf].l=min(fst[l],fst[r]),f[fzf].r=max(fst[l],fst[r]);
f[fzf].k=qfz,f[fzf].num=fzf;
}
}
sort(f+1,f+1+fzf);
int l=0,r=0,k=0,fansq=0;
for(int i=1;i<=fzf;++i){
while(l>f[i].l){
--l;++cqfz[dfn[l]];
if(cqfz[dfn[l]]==2){
fansq-=fv[fc[dfn[l]]]*fw[fzans[fc[dfn[l]]]];
--fzans[fc[dfn[l]]];
}
if(cqfz[dfn[l]]==1){
++fzans[fc[dfn[l]]];
fansq+=fv[fc[dfn[l]]]*fw[fzans[fc[dfn[l]]]];
}
}
while(l<f[i].l){
--cqfz[dfn[l]];
if(cqfz[dfn[l]]==0){
fansq-=fv[fc[dfn[l]]]*fw[fzans[fc[dfn[l]]]];
--fzans[fc[dfn[l]]];
}
if(cqfz[dfn[l]]==1){
++fzans[fc[dfn[l]]];
fansq+=fv[fc[dfn[l]]]*fw[fzans[fc[dfn[l]]]];
}
++l;
}
while(r<f[i].r){
++r;++cqfz[dfn[r]];
if(cqfz[dfn[r]]==2){
fansq-=fv[fc[dfn[r]]]*fw[fzans[fc[dfn[r]]]];
--fzans[fc[dfn[r]]];
}
if(cqfz[dfn[r]]==1){
++fzans[fc[dfn[r]]];
fansq+=fv[fc[dfn[r]]]*fw[fzans[fc[dfn[r]]]];
}
}
while(r>f[i].r){
--cqfz[dfn[r]];
if(cqfz[dfn[r]]==0){
fansq-=fv[fc[dfn[r]]]*fw[fzans[fc[dfn[r]]]];
--fzans[fc[dfn[r]]];
}
if(cqfz[dfn[r]]==1){
++fzans[fc[dfn[r]]];
fansq+=fv[fc[dfn[r]]]*fw[fzans[fc[dfn[r]]]];
}
--r;
}
while(k<f[i].k){
++k;
if(cqfz[fz[k].x]==1){
fansq-=fv[fc[fz[k].x]]*fw[fzans[fc[fz[k].x]]];
--fzans[fc[fz[k].x]];
++fzans[fz[k].y];
fansq+=fv[fz[k].y]*fw[fzans[fz[k].y]];
}
swap(fc[fz[k].x],fz[k].y);
}
while(k>f[i].k){
if(cqfz[fz[k].x]==1){
fansq-=fv[fc[fz[k].x]]*fw[fzans[fc[fz[k].x]]];
--fzans[fc[fz[k].x]];
++fzans[fz[k].y];
fansq+=fv[fz[k].y]*fw[fzans[fz[k].y]];
}
swap(fc[fz[k].x],fz[k].y);
--k;
}
int fffff=fansq;
int llca=lca(f[i].x,f[i].y);
if(llca==f[i].x||llca==f[i].y){
fans[f[i].num]=fffff;
continue;
}
int _fz=fw[fzans[fc[llca]]+1ll];
fffff+=_fz*fv[fc[llca]];
int xx=f[i].x,yy=f[i].y;
if(fst[xx]>fst[yy])swap(xx,yy);
_fz=fw[fzans[fc[xx]]+1ll];
fffff+=_fz*fv[fc[xx]];
fans[f[i].num]=fffff;
}
for(int i=1;i<=fzf;++i)printf("%lld\n",fans[i]);
return 0;
}
by Wyxrg @ 2021-12-09 21:43:57
@寺中言
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline void read(int &x){
x=0;
int y=1;
char a;
a=getchar();
while(a<'0'||a>'9'){
if(a=='-')y=-1;
a=getchar();
}
while(a>='0'&&a<='9'){
x=x*10+a-'0';
a=getchar();
}
x*=y;
}
int n,m,q;
int fv[100008],fw[100008];
vector<int>ff[100008];
int dfn[200008],fst[100008],fed[100008];
int qfz,fzf;
void dfsq(int x,int fa){
++qfz;
dfn[qfz]=x;
fst[x]=qfz;
for(int i=0;i<ff[x].size();++i){
int y=ff[x][i];
if(y==fa)continue;
dfsq(y,x);
}
++qfz;
dfn[qfz]=x;
fed[x]=qfz;
}
int fdp[100008][21],fd[100008];
void dfsq1(int x,int fa){
fdp[x][0]=fa;fd[x]=fd[fa]+1;
for(int i=1;i<=20;++i){
fdp[x][i]=fdp[fdp[x][i-1]][i-1];
}
for(int i=0;i<ff[x].size();++i){
int y=ff[x][i];
if(y==fa)continue;
dfsq1(y,x);
}
}
int lca(int x,int y){
if(fd[x]<fd[y])swap(x,y);
for(int i=20;i>=0;--i){
if(fd[fdp[x][i]]>=fd[y])x=fdp[x][i];
}
if(x==y)return x;
for(int i=19;i>=0;--i){
if(fdp[x][i]!=fdp[y][i])x=fdp[x][i],y=fdp[y][i];
}
return fdp[x][0];
}
int fc[100008];
int fzn;
struct ffff{
int x,y;
int l,r,k;
int num;
bool operator <(const ffff &x)const{
if(l/fzn==x.l/fzn&&r/fzn==x.r/fzn)return k<x.k;
if(l/fzn==x.l/fzn)return r/fzn<x.r/fzn;
return l/fzn<x.l/fzn;
}
}f[100008];
struct fffz{
int x,y;
}fz[100008];
int fzans[100008];
int cqfz[100008];
long long fans[100008];
signed main(){
read(n);read(m);read(q);
n*=2;fzn=pow(n,0.666);n/=2;
for(int i=1;i<=m;++i)read(fv[i]);
for(int i=1;i<=n;++i)read(fw[i]);
for(int i=1;i<n;++i){
int a,b;read(a);read(b);
ff[a].push_back(b);
ff[b].push_back(a);
}
dfsq(1,0);
dfsq1(1,0);
for(int i=1;i<=n;++i)read(fc[i]);
qfz=0;
for(int i=1;i<=q;++i){
int ty;read(ty);
if(ty==0){
++qfz;
read(fz[qfz].x);read(fz[qfz].y);
}
if(ty==1){
++fzf;
int l,r;read(l);read(r);
f[fzf].x=l,f[fzf].y=r;
int LCA=lca(l, r);
if(fst[l]>fst[r]) swap(l,r);
if(LCA==l||LCA==r) f[fzf].l=fst[l],f[fzf].r=fst[r];
else f[fzf].l=fed[l],f[fzf].r=fst[r];
f[fzf].k=qfz,f[fzf].num=fzf;
}
}
sort(f+1,f+1+fzf);
int l=0,r=0,k=0,fansq=0;
for(int i=1;i<=fzf;++i){
while(l>f[i].l){
--l;++cqfz[dfn[l]];
if(cqfz[dfn[l]]==2){
fansq-=fv[fc[dfn[l]]]*fw[fzans[fc[dfn[l]]]];
--fzans[fc[dfn[l]]];
}
if(cqfz[dfn[l]]==1){
++fzans[fc[dfn[l]]];
fansq+=fv[fc[dfn[l]]]*fw[fzans[fc[dfn[l]]]];
}
}
while(l<f[i].l){
--cqfz[dfn[l]];
if(cqfz[dfn[l]]==0){
fansq-=fv[fc[dfn[l]]]*fw[fzans[fc[dfn[l]]]];
--fzans[fc[dfn[l]]];
}
if(cqfz[dfn[l]]==1){
++fzans[fc[dfn[l]]];
fansq+=fv[fc[dfn[l]]]*fw[fzans[fc[dfn[l]]]];
}
++l;
}
while(r<f[i].r){
++r;++cqfz[dfn[r]];
if(cqfz[dfn[r]]==2){
fansq-=fv[fc[dfn[r]]]*fw[fzans[fc[dfn[r]]]];
--fzans[fc[dfn[r]]];
}
if(cqfz[dfn[r]]==1){
++fzans[fc[dfn[r]]];
fansq+=fv[fc[dfn[r]]]*fw[fzans[fc[dfn[r]]]];
}
}
while(r>f[i].r){
--cqfz[dfn[r]];
if(cqfz[dfn[r]]==0){
fansq-=fv[fc[dfn[r]]]*fw[fzans[fc[dfn[r]]]];
--fzans[fc[dfn[r]]];
}
if(cqfz[dfn[r]]==1){
++fzans[fc[dfn[r]]];
fansq+=fv[fc[dfn[r]]]*fw[fzans[fc[dfn[r]]]];
}
--r;
}
while(k<f[i].k){
++k;
if(cqfz[fz[k].x]==1){
fansq-=fv[fc[fz[k].x]]*fw[fzans[fc[fz[k].x]]];
--fzans[fc[fz[k].x]];
++fzans[fz[k].y];
fansq+=fv[fz[k].y]*fw[fzans[fz[k].y]];
}
swap(fc[fz[k].x],fz[k].y);
}
while(k>f[i].k){
if(cqfz[fz[k].x]==1){
fansq-=fv[fc[fz[k].x]]*fw[fzans[fc[fz[k].x]]];
--fzans[fc[fz[k].x]];
++fzans[fz[k].y];
fansq+=fv[fz[k].y]*fw[fzans[fz[k].y]];
}
swap(fc[fz[k].x],fz[k].y);
--k;
}
int fffff=fansq;
int llca=lca(f[i].x,f[i].y);
if(llca==f[i].x||llca==f[i].y){
fans[f[i].num]=fffff;
continue;
}
int _fz=fw[fzans[fc[llca]]+1ll];
fffff+=_fz*fv[fc[llca]];
fans[f[i].num]=fffff;
}
for(int i=1;i<=fzf;++i)printf("%lld\n",fans[i]);
return 0;
}by Wyxrg @ 2021-12-10 09:26:52
同时处理