zzzing @ 2019-03-14 21:20:59

by nofall @ 2019-03-14 21:21:15

希望更丰富的展现？使用Markdown

by zzzing @ 2019-03-14 22:05:25

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#define ll long long
const int MAXN=2e5+10;
using namespace std;
int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0', ch=getchar();
    return x*f;
}
int N,M,Q,sz;
int V[MAXN],W[MAXN],C2[MAXN],C[MAXN];
ll sum[MAXN];
//
vector<int> edge[MAXN];
int a[2*MAXN],in[MAXN],out[MAXN],timeclock=0;
int g[MAXN][30],dep[MAXN];
void dfs(int now,int deep)
{
    a[++timeclock]=now; in[now]=timeclock; dep[now]=deep;
    for(int i=1;i<=20;i++)
        g[now][i]=g[g[now][i-1]][i-1];
    for(int i=0;i<edge[now].size();i++)
    {
        int t=edge[now][i];
        if(g[now][0]==t) continue;
        g[t][0]=now;
        dfs(t,deep+1);
    }
    a[++timeclock]=now; out[now]=timeclock;
}
int LCA(int a,int b)
{
    if(dep[a]<dep[b]) swap(a,b);
    for(int i=20;i>=0;i--)
        if(dep[g[a][i]]>=dep[b])
            a=g[a][i];
    for(int i=20;i>=0;i--)
        if(g[a][i]!=g[b][i])
            a=g[a][i], b=g[b][i];
    if(a!=b) a=g[a][0];
    return a;
}
//
int cnt1=0,cnt2=0,vt[MAXN],num[MAXN];
ll ans[MAXN],Ans=0;
struct node1
{
    int x,id,k0,k1;
}a1[MAXN];
struct node2
{
    int l,r,id,lca;
}a2[MAXN];
bool cmp(node2 x,node2 y)
{
    if(x.l/sz!=y.l/sz) return x.l/sz<y.l/sz;
    if(x.r/sz!=y.r/sz) return x.r/sz<y.r/sz;
    return x.id<y.id;
}
void update(int p)
{
    vt[a[p]]^=1;
    if(vt[a[p]])
    {
        num[C[a[p]]]++;
        Ans+=(ll)V[C[a[p]]]*(ll)(sum[num[C[a[p]]]]-sum[num[C[a[p]]]-1]);
    }
    else
    {
        num[C[a[p]]]--;
        Ans+=(ll)V[C[a[p]]]*(ll)(sum[num[C[a[p]]]]-sum[num[C[a[p]]]+1]);
    }
}
int main()
{
    //freopen("p4074.in","r",stdin);
    //freopen("p4074.out","w",stdout);
    memset(ans,-1,sizeof(ans));
    N=read(), M=read(), Q=read();
    for(int i=1;i<=M;i++) V[i]=read();
    for(int i=1;i<=N;i++) W[i]=read(), sum[i]=sum[i-1]+(ll)W[i];
    for(int i=1;i<N;i++)
    {
        int u=read(),v=read();
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    for(int i=1;i<=N;i++) C[i]=C2[i]=read();
    dfs(1,1);
    for(int i=1;i<=Q;i++)
    {
        int opt=read();
        if(opt==0)
        {
            cnt1++;
            a1[cnt1].k0=C2[a1[cnt1].x=read()], a1[cnt1].k1=read(), a1[cnt1].id=i;
            C2[a1[cnt1].x]=a1[cnt1].k1;
        }
        if(opt==1)
        {
            cnt2++;
            int x=read(), y=read(); a2[cnt2].lca=LCA(x,y);
            if(in[x]>in[y]) swap(x,y);
            a2[cnt2].l=out[x]<in[y]?out[x]:in[x], a2[cnt2].r=in[y], a2[cnt2].id=i;
        }
    }
    sz=ceil(exp((log(2*N)+log(cnt2))/3));
    sort(a2+1,a2+1+cnt2,cmp);
    int l=1,r=0,t=0;
    for(int i=1;i<=cnt2;i++)
    {
        while(a1[t+1].id<a2[i].id&&t<cnt1)
        {
            t++;
            C[a1[t].x]=a1[t].k1;
            if(vt[a1[t].x])
            {
                num[a1[t].k0]--, num[a1[t].k1]++;
                Ans+=(ll)V[a1[t].k1]*(ll)(sum[num[a1[t].k1]]-sum[num[a1[t].k1]-1])+(ll)V[a1[t].k0]*(ll)(sum[num[a1[t].k0]]-sum[num[a1[t].k0]+1]);
            }
        }
        while(a1[t].id>a2[i].id)
        {
            C[a1[t].x]=a1[t].k0;
            if(vt[a1[t].x])
            {
                num[a1[t].k1]--, num[a1[t].k0]++;
                Ans+=(ll)V[a1[t].k1]*(ll)(sum[num[a1[t].k1]]-sum[num[a1[t].k1]+1])+(ll)V[a1[t].k0]*(ll)(sum[num[a1[t].k0]]-sum[num[a1[t].k0]-1]);
            }
            t--;
        }
        while(l<a2[i].l) update(l++);
        while(r>a2[i].r) update(r--);
        while(l>a2[i].l) update(--l);
        while(r<a2[i].r) update(++r);
        ans[a2[i].id]=Ans;
        if(a2[i].lca==a[a2[i].l]||a2[i].lca==a[a2[i].r]) continue;
        ans[a2[i].id]+=(ll)V[C[a2[i].lca]]*(ll)(sum[num[C[a2[i].lca]]+1]-sum[num[C[a2[i].lca]]]);
    }
    for(int i=1;i<=Q;i++)
        if(ans[i]!=-1) printf("%lld\n",ans[i]);
}
``````cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#define ll long long
const int MAXN=2e5+10;
using namespace std;
int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0', ch=getchar();
    return x*f;
}
int N,M,Q,sz;
int V[MAXN],W[MAXN],C2[MAXN],C[MAXN];
ll sum[MAXN];
//
vector<int> edge[MAXN];
int a[2*MAXN],in[MAXN],out[MAXN],timeclock=0;
int g[MAXN][30],dep[MAXN];
void dfs(int now,int deep)
{
    a[++timeclock]=now; in[now]=timeclock; dep[now]=deep;
    for(int i=1;i<=20;i++)
        g[now][i]=g[g[now][i-1]][i-1];
    for(int i=0;i<edge[now].size();i++)
    {
        int t=edge[now][i];
        if(g[now][0]==t) continue;
        g[t][0]=now;
        dfs(t,deep+1);
    }
    a[++timeclock]=now; out[now]=timeclock;
}
int LCA(int a,int b)
{
    if(dep[a]<dep[b]) swap(a,b);
    for(int i=20;i>=0;i--)
        if(dep[g[a][i]]>=dep[b])
            a=g[a][i];
    for(int i=20;i>=0;i--)
        if(g[a][i]!=g[b][i])
            a=g[a][i], b=g[b][i];
    if(a!=b) a=g[a][0];
    return a;
}
//
int cnt1=0,cnt2=0,vt[MAXN],num[MAXN];
ll ans[MAXN],Ans=0;
struct node1
{
    int x,id,k0,k1;
}a1[MAXN];
struct node2
{
    int l,r,id,lca;
}a2[MAXN];
bool cmp(node2 x,node2 y)
{
    if(x.l/sz!=y.l/sz) return x.l/sz<y.l/sz;
    if(x.r/sz!=y.r/sz) return x.r/sz<y.r/sz;
    return x.id<y.id;
}
void update(int p)
{
    vt[a[p]]^=1;
    if(vt[a[p]])
    {
        num[C[a[p]]]++;
        Ans+=(ll)V[C[a[p]]]*(ll)(sum[num[C[a[p]]]]-sum[num[C[a[p]]]-1]);
    }
    else
    {
        num[C[a[p]]]--;
        Ans+=(ll)V[C[a[p]]]*(ll)(sum[num[C[a[p]]]]-sum[num[C[a[p]]]+1]);
    }
}
int main()
{
    //freopen("p4074.in","r",stdin);
    //freopen("p4074.out","w",stdout);
    memset(ans,-1,sizeof(ans));
    N=read(), M=read(), Q=read();
    for(int i=1;i<=M;i++) V[i]=read();
    for(int i=1;i<=N;i++) W[i]=read(), sum[i]=sum[i-1]+(ll)W[i];
    for(int i=1;i<N;i++)
    {
        int u=read(),v=read();
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    for(int i=1;i<=N;i++) C[i]=C2[i]=read();
    dfs(1,1);
    for(int i=1;i<=Q;i++)
    {
        int opt=read();
        if(opt==0)
        {
            cnt1++;
            a1[cnt1].k0=C2[a1[cnt1].x=read()], a1[cnt1].k1=read(), a1[cnt1].id=i;
            C2[a1[cnt1].x]=a1[cnt1].k1;
        }
        if(opt==1)
        {
            cnt2++;
            int x=read(), y=read(); a2[cnt2].lca=LCA(x,y);
            if(in[x]>in[y]) swap(x,y);
            a2[cnt2].l=out[x]<in[y]?out[x]:in[x], a2[cnt2].r=in[y], a2[cnt2].id=i;
        }
    }
    sz=ceil(exp((log(2*N)+log(cnt2))/3));
    sort(a2+1,a2+1+cnt2,cmp);
    int l=1,r=0,t=0;
    for(int i=1;i<=cnt2;i++)
    {
        while(a1[t+1].id<a2[i].id&&t<cnt1)
        {
            t++;
            C[a1[t].x]=a1[t].k1;
            if(vt[a1[t].x])
            {
                num[a1[t].k0]--, num[a1[t].k1]++;
                Ans+=(ll)V[a1[t].k1]*(ll)(sum[num[a1[t].k1]]-sum[num[a1[t].k1]-1])+(ll)V[a1[t].k0]*(ll)(sum[num[a1[t].k0]]-sum[num[a1[t].k0]+1]);
            }
        }
        while(a1[t].id>a2[i].id)
        {
            C[a1[t].x]=a1[t].k0;
            if(vt[a1[t].x])
            {
                num[a1[t].k1]--, num[a1[t].k0]++;
                Ans+=(ll)V[a1[t].k1]*(ll)(sum[num[a1[t].k1]]-sum[num[a1[t].k1]+1])+(ll)V[a1[t].k0]*(ll)(sum[num[a1[t].k0]]-sum[num[a1[t].k0]-1]);
            }
            t--;
        }
        while(l<a2[i].l) update(l++);
        while(r>a2[i].r) update(r--);
        while(l>a2[i].l) update(--l);
        while(r<a2[i].r) update(++r);
        ans[a2[i].id]=Ans;
        if(a2[i].lca==a[a2[i].l]||a2[i].lca==a[a2[i].r]) continue;
        ans[a2[i].id]+=(ll)V[C[a2[i].lca]]*(ll)(sum[num[C[a2[i].lca]]+1]-sum[num[C[a2[i].lca]]]);
    }
    for(int i=1;i<=Q;i++)
        if(ans[i]!=-1) printf("%lld\n",ans[i]);
}