PanH @ 2020-05-25 14:47:23
写的代码出了一亿点问题，后面7个点都T了，可是试了O2，O3，都会运行错误，而我加了一句
#pragma GCC optimize(1)之后竟然多过了3个点，请问大佬们这是什么情况啊qwq。
by PanH @ 2020-05-25 14:48:12
code：
#pragma GCC optimize(1)
#include<bits/stdc++.h>
using namespace std;
template<class T>inline void read(T &x)
{
x=0;int f=0;char ch=getchar();
while(!isdigit(ch)) f=(ch=='-'),ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=f?-x:x;
}
const int N=2e5+5;
struct edge{
int next,to;
}e[N<<1];
int head[N],cnt,V[N],W[N],C[N],n,tot,num,bel[N],rev[2][N],f[N][21],dep[N],eu[N],vis[N],co[N],m,q,a[N];
long long res,ans[N];
struct question{
int l,r,lca,t,id;
bool operator < (const question x) const {return bel[l]==bel[x.l]?(bel[r]==bel[x.r]?t<x.t:bel[r]<bel[x.r]):bel[l]<bel[x.l];}
}que[N];
struct change{
int pos,from,to;
}tra[N];
inline void add(int u,int v)
{
e[++cnt]=(edge){head[u],v};
head[u]=cnt;
}
void dfs(int x,int fa)
{
eu[++tot]=x,rev[0][x]=tot,f[x][0]=fa,dep[x]=dep[fa]+1;
// cout<<x<<endl;
for(int i=1;i<=20;i++) f[x][i]=f[f[x][i-1]][i-1];
for(int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
// cout<<y<<endl;
if(dep[y]) continue;
dfs(y,x);
// cout<<x<<' '<<fa<<endl;
}
eu[++tot]=x,rev[1][x]=tot;
return;
}
inline int LCA(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;i>=0;i--)
if(dep[f[x][i]]>=dep[y])
x=f[x][i];
if(x==y) return x;
for(int i=20;i>=0;i--)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
inline void Change(int k)
{
if(vis[k]^=1) res=(res+1ll*W[++co[C[k]]]*V[C[k]]);
else res=(res-1ll*W[co[C[k]]--]*V[C[k]]);
}
inline void Time_go(int k)
{
if(vis[tra[k].pos])
{
Change(tra[k].pos);
C[tra[k].pos]=tra[k].to;
Change(tra[k].pos);
}
else C[tra[k].pos]=tra[k].to;
}
inline void Time_back(int k)
{
if(vis[tra[k].pos])
{
Change(tra[k].pos);
C[tra[k].pos]=tra[k].from;
Change(tra[k].pos);
}
else C[tra[k].pos]=tra[k].from;
}
int main()
{
// freopen("!.in","r",stdin);
read(n),read(m),read(q);
// scanf("%lld",&n),scanf("%lld",&m),scanf("%lld",&q);
for(int i=1;i<=m;i++) read(V[i]);
//scanf("%lld",&V[i]);
for(int i=1;i<=n;i++) read(W[i]);
//scanf("%lld",&W[i]);
for(int i=1;i<n;i++)
{
int u,v;
read(u),read(v);
// scanf("%lld",&u),scanf("%lld",&v);
add(u,v),add(v,u);
}
for(int i=1;i<=n;i++)
{
// scanf("%lld",&C[i]);
// cout<<C[i]<<endl;
read(C[i]);
a[i]=C[i];
// cout<<C[i]<<endl;
}
dfs(1,0);
// cout<<"!";
for(int i=1,len=pow(tot,2.0/3);i<=n;i++) bel[i]=(i-1)/len+1;
for(int i=1,k=0;i<=q;i++)
{
int op;
// scanf("%lld",&op);
read(op);
if(op==0) k++,read(tra[k].pos),read(tra[k].to),tra[k].from=a[tra[k].pos],a[tra[k].pos]=tra[k].to;
else
{
int x,y;que[++num].t=k,que[num].id=num;
read(x),read(y);
// scanf("%lld",&x),scanf("%lld",&y);
if(dep[x]<dep[y]) swap(x,y);
int lca=LCA(x,y);
if(lca==y) que[num].l=rev[0][y],que[num].r=rev[0][x];
else
if(rev[0][x]<rev[0][y]) que[num].l=rev[1][x],que[num].r=rev[0][y],que[num].lca=lca;
else que[num].l=rev[1][y],que[num].r=rev[0][x],que[num].lca=lca;
}
}
sort(que+1,que+num+1);
for(int i=1,l=1,r=0,t=0;i<=num;i++)
{
while(t<que[i].t) Time_go(++t);
while(t>que[i].t) Time_back(t--);
while(l<que[i].l) Change(eu[l++]);
while(r>que[i].r) Change(eu[r--]);
while(l>que[i].l) Change(eu[--l]);
while(r<que[i].r) Change(eu[++r]);
if(que[i].lca) Change(que[i].lca),ans[que[i].id]=res,Change(que[i].lca);
else ans[que[i].id]=res;
}
for(int i=1;i<=num;i++) printf("%lld\n",ans[i]);
return 0;
}by PanH @ 2020-05-25 14:51:07
代码很丑，如果嫌长大佬们可以不看，但要是遇到过相似情况能不能给蒟蒻提点建议呀pwp
by 傅天宇 @ 2020-05-25 15:04:39
那就都写上去把/xyx
by PanH @ 2020-05-25 15:05:59
@唯有呵呵 试了，会运行错误（
by 奇米 @ 2020-05-25 15:06:42
树上莫队神仙，小蒟蒻根本无法同台竞技
by PanH @ 2020-05-25 15:07:29
开始演了？
by Froggy @ 2020-05-25 15:12:24
UB吧
by 傅天宇 @ 2020-05-25 15:13:32
@panhan 啊这
by PanH @ 2020-05-25 15:14:26
@Froggy UB是什么呀
by Froggy @ 2020-05-25 15:29:38
@panhan
https://studyingfather.blog.luogu.org/undefined-behavior