forever_dreams @ 2018-07-01 23:10:08

by forever_dreams @ 2018-07-01 23:11:36

//洛谷 P4074 糖果公园 
#include<cmath>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int Read()
{
    int i=0,f=1;
    char c;
    for(c=getchar();c!='-'&&!isdigit(c);c=getchar());
    if(c=='-')
    {
        f=-1;
        c=getchar();
    }
    for(;isdigit(c);c=getchar())
      i=(i<<1)+(i<<3)+c-'0';
    return i*f;
}
const int N=100005,M=100005,Q=100005;
int n,m,q,s,cnt,sum;
int a[Q],b[Q],c[M],v[N],w[N],id[N],ans[Q],cou[N],val[Q],last[Q],type[Q];
int bottom,top,dep[N],fa[N][18];
int t=0,first[N],to[2*N],next[2*N];
bool sta[N];
struct node
{
    int x,y,bl,br,num;
}query[Q];
int cmp(const node &p,const node &q)
{
    if(p.bl!=q.bl)  return p.bl<q.bl;
    if(p.br!=q.br)  return p.br<q.br;
    return p.num<q.num;
}
void add(int x,int y)
{
    next[++t]=first[x];first[x]=t;to[t]=y;
    next[++t]=first[y];first[y]=t;to[t]=x;
}
void dfs(int x,int father)
{
    int i,y,bottom=top;
    dep[x]=dep[father]+1;
    for(i=0;fa[x][i];++i)
      fa[x][i+1]=fa[fa[x][i]][i];
    for(i=first[x];i;i=next[i])
    {
        y=to[i];
        if(y==father)
          continue;
        dfs(y,x);
        if(top-bottom>=s)
        {
            sum++;
            while(top>bottom)
              id[sta[top--]]=sum;
        }
    }
    sta[++top]=x;
}
int lca(int x,int y)
{
    int i;
    if(dep[x]<dep[y])  swap(x,y);
    for(i=17;i>=0;--i)
      if(dep[fa[x][i]]>=dep[y])
        x=fa[x][i];
    if(x==y)  return x;
    for(i=17;i>=0;--i)
    {
        if(fa[x][i]!=fa[y][i])
        {
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}
void rev(int x)
{
    cnt-=w[cou[c[x]]]*v[c[x]];
    sta[x]?--cou[c[x]]:++cou[c[x]];
    sta[x]=!sta[x];
    cnt+=w[cou[c[x]]]*v[c[x]];
}
void solve(int x,int y)
{
    int z=lca(x,y);
    while(x!=z)  rev(x),x=fa[x][0];
    while(y!=z)  rev(y),y=fa[y][0];
}
void modify(int x,int y)
{
    if(!sta[x])
    {
        c[x]=y;
        return;
    }
    rev(x);
    c[x]=y;
    rev(x);
}
int upt(int tarT,int curT)
{
    while(curT<tarT)
    {
        curT++;
        if(!type[curT])
          modify(a[curT],b[curT]);
    }
    while(curT>tarT)
    {
        if(!type[curT])
          modify(a[curT],last[curT]);
        curT--;
    }
}
int main()
{
    int i,z,tot=0;
    n=Read();m=Read();q=Read();
    s=pow(n,2.0/3.0);
    for(i=1;i<=m;++i)  v[i]=Read();
    for(i=1;i<=n;++i)  w[i]=Read();
    for(i=2;i<=n;++i)  w[i]+=w[i-1];
    for(i=1;i<n;++i)  add(Read(),Read());
    for(i=1;i<=n;++i)  val[i]=c[i]=Read();
    dfs(1,0);
    while(top)
      id[sta[top--]]=sum;
    for(i=1;i<=q;++i)
    {
        scanf("%d%d%d",&type[i],&a[i],&b[i]);
        if(type[i])
        {
            tot++;
            if(id[a[i]]>id[b[i]])  swap(a[i],b[i]);
            query[tot].x=a[i];
            query[tot].y=b[i];
            query[tot].bl=id[a[i]];
            query[tot].br=id[b[i]];
            query[tot].num=i;
        }
        else
        {
            last[i]=val[a[i]];
            val[a[i]]=b[i];
        }
    }
    sort(query+1,query+tot+1,cmp);
    for(i=1;i<=tot;++i)
    {
        upt(query[i].num,query[i-1].num);
        solve(query[i].x,query[i-1].x);
        solve(query[i].y,query[i-1].y);
        z=lca(query[i].x,query[i].y);
        rev(z);
        ans[query[i].num]=cnt;
        rev(z);
    }
    for(i=1;i<=q;++i)
      if(type[i])
        printf("%d\n",ans[i]);
    return 0;
}

by ldxcaicai @ 2018-07-02 00:34:55

唔，你可以看看lyh的pdf啊

by forever_dreams @ 2018-07-02 07:42:18

@ldxoi 唔 谢谢