mendessy @ 2019-07-30 12:56:05
（再调不出来就女装)（是不可能的）
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define ll long long
using namespace std;
const int maxn=100010;
const int maxm=1e6+10;
int n,m,ques,s,tim,anss;
struct nmsl{
int l,r,bl,id,lca,times,ans;
inline bool operator<(const nmsl &ikunkun)const
{
if(bl==ikunkun.bl)
return r<ikunkun.r || r==ikunkun.r && times<ikunkun.times;
else
return bl<ikunkun.bl;
}
}q[maxn];//以l所属的块为第一关键字，r为第二关键字，times为第三关键字排序
struct cxknmsl{
int x,y;
}history[maxn];//存储改变语句
int v[maxn],w[maxn],c[maxn],first[maxn*2],next[maxn*2],to[maxn*2],tot;
int deep[maxn],fa[maxn],son[maxn],size[maxn],start[maxn],end[maxn],oula[maxn];
int cxk[maxn],happen[maxm],used[maxm],top[maxn];
int read()
{
int f=1,x=0;
char ch=getchar();
while(ch<'0' || ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
void add(int x,int y)
{
tot++;
next[tot]=first[x];
first[x]=tot;
to[tot]=y;
}
void dfs1(int now,int father)
{
size[now]=1;
fa[now]=father;
start[now]=++tot;oula[tot]=now;
for(int i=first[now];i;i=next[i])
{
int x=to[i];
if(deep[x]) continue;
deep[x]=deep[now]+1;
dfs1(x,now);
size[x]+=size[now];
if(size[son[now]]<size[x])
son[now]=x;
}
end[now]=++tot;oula[tot]=now;
}
void dfs2(int now,int fatop)
{
top[now]=fatop;
if(son[now])
dfs2(son[now],fatop);
for(int i=first[now];i;i=next[i])
{
int x=to[i];
if(x==fa[now] || x==son[now])
continue;
dfs2(x,x);
}
}
//两个dfs解决树剖与欧拉序（好像不是欧拉序但我不管了）
int LCA(int x,int y)
{
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]])
swap(x,y);
x=fa[top[x]];
}
return deep[x]<deep[y]?x:y;
}
//找lca
void delet(int ilovekk)
{
anss-=w[happen[ilovekk]]*ilovekk;
happen[ilovekk]--;
anss+=w[happen[ilovekk]]*ilovekk;
}
//删除
void add(int ilovekk)
{
anss-=w[happen[ilovekk]]*ilovekk;
happen[ilovekk]++;
anss+=w[happen[ilovekk]]*ilovekk;
}
//加入
void Add(int x)
{
used[x]?delet(c[x]):add(c[x]);
used[x]^=1;
}
//判断是否在欧拉序中出现两次by mendessy @ 2019-07-30 12:56:45
int main()
{
n=read();m=read();ques=read();
s=pow(n,2.0/3.0)*0.5;
for(int i=1;i<=m;i++)
v[i]=read();
for(int i=1;i<=n;i++)
w[i]=read();
for(int i=2;i<=n;i++)
w[i]+=w[i-1];
for(int i=1;i<=n-1;i++)
{
int x,y;
x=read();y=read();
add(x,y);add(y,x);
}
for(int i=1;i<=n;i++)
c[i]=read();
for(int i=1;i<=n;i++)
c[i]=v[c[i]];
deep[1]=1;tot=0;
dfs1(1,0);
dfs2(1,1);
tim=0;tot=0;
for(int i=1;i<=ques;i++)
{
int l,r,lca,type;
type=read();l=read();r=read();
if(type==1)
{
if(start[l]>start[r])
swap(l,r);
lca=LCA(l,r);
if(lca==l)
{
q[++tot].id=tot;
q[tot].l=start[l];
q[tot].r=start[r];
q[tot].bl=(q[tot].l-1)/s+1;
q[tot].times=tim;
}
else
{
q[++tot].id=tot;
q[tot].l=end[l];
q[tot].r=start[r];
q[tot].bl=(q[tot].l-1)/s+1;
q[tot].times=tim;
q[tot].lca=lca;
}
}
else
{
tim++;
history[tim].x=l;
history[tim].y=v[r];
}
}
sort(q+1,q+1+tot);
int timenow=0,l=0,r=0;anss=0;
int flag=0;
//蒟蒻的可爱莫队
for(int i=1;i<=tot;i++)
{
while(timenow<q[i].times)
{
timenow++;
if(used[history[timenow].x]==1)
Add(history[timenow].x),flag=1;
int change=c[history[timenow].x];
c[history[timenow].x]=history[timenow].y;
history[timenow].y=change;
if(flag==1)
Add(history[timenow].x),flag=0;
}
while(timenow>q[i].times)
{
if(used[history[timenow].x]==1)
Add(history[timenow].x),flag=1;
int change=c[history[timenow].x];
c[history[timenow].x]=history[timenow].y;
history[timenow].y=change;
if(flag==1)
Add(history[timenow].x),flag=0;
timenow--;
}//处理上个询问时间与这个询问时间
//接下来就是普通树上莫队
while(l>q[i].l)
{
l--;
Add(oula[l]);
}
while(l<q[i].l)
{
Add(oula[l]);
l++;
}
while(r>q[i].r)
{
Add(oula[r]);
r--;
}
while(r<q[i].r)
{
r++;
Add(oula[r]);
}
if(q[i].lca)
Add(q[i].lca);
q[i].ans=anss;
if(q[i].lca)
Add(q[i].lca);
}
//用cxk存储答案
for(int i=1;i<=tot;i++)
cxk[q[i].id]=q[i].ans;
for(int i=1;i<=tot;i++)
printf("%d\n",cxk[i]);//输出
return 0;
}太长了一次发不完
by FZzzz @ 2019-07-30 13:01:54
大家别帮楼主，看他女装
by tryrtj @ 2019-07-30 13:11:58
你跳不出来代表你调出来了
by mendessy @ 2019-07-30 14:11:55
@tryrtj 我是真的调不出来了。