Aragorn‘s Story

#include <iostream>#include <algorithm>#include <cstdio>#include <queue>#include <cmath>#include <map>#include <iterator>#include <cstring>#include <string>using namespace std;#pragma comment(linker, "/STACK:1024000000,1024000000") //手动加栈、windows系统容易爆栈#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define INF 0x7fffffff#define ll long long#define N 50005struct Edge{    int to,next;}edge[N<<1];int head[N],tot;int num[N];int pos;int fa[N];int son[N];int p[N];int fp[N];int deep[N];int size[N];int top[N];int n,m,q;void add(int x,int y){    edge[tot].to=y;    edge[tot].next=head[x];    head[x]=tot++;}void init(){    tot=0;    pos=1;    memset(head,-1,sizeof(head));    memset(son,-1,sizeof(son));}void dfs1(int now,int pre,int d)  //找出重边{    deep[now]=d;    fa[now]=pre;    size[now]=1;    for(int i=head[now];i!=-1;i=edge[i].next)    {        int next=edge[i].to;        if(next!=pre)        {            dfs1(next,now,d+1);            size[now]+=size[next];            if(son[now]==-1 || size[next]>size[son[now]])            {                son[now]=next;            }        }    }}void dfs2(int now,int tp)         //连重边成重链，把所有的重链首尾连在一起，并离散到线段树区间中{    top[now]=tp;    p[now]=pos++;    fp[p[now]]=now;    if(son[now]==-1) return;    dfs2(son[now],tp);    for(int i=head[now];i!=-1;i=edge[i].next)    {        int next=edge[i].to;        if(son[now]!=next && next!=fa[now])        {            dfs2(next,next);        }    }}int sum[N<<2];int col[N<<2];void pushup(int rt){    sum[rt]=sum[rt<<1]+sum[rt<<1|1];}void pushdown(int l,int r,int rt){    int m=(l+r)>>1;    if(col[rt])    {        col[rt<<1]+=col[rt];        col[rt<<1|1]+=col[rt];        sum[rt<<1]+=(m-l+1)*col[rt];        sum[rt<<1|1]+=(r-m)*col[rt];        col[rt]=0;    }}void build(int l,int r,int rt){    col[rt]=0;    if(l==r)    {        sum[rt]=num[fp[l]];        return;    }    int m=(l+r)>>1;    build(l,m,rt<<1);    build(m+1,r,rt<<1|1);    pushup(rt);}void update(int l,int r,int rt,int L,int R,int c){    if(l==L && r==R)    {        col[rt]+=c;        sum[rt]+=(r-l+1)*c;        return;    }    pushdown(l,r,rt);    int m=(l+r)>>1;    if(R<=m) update(l,m,rt<<1,L,R,c);    else if(L>m) update(m+1,r,rt<<1|1,L,R,c);    else    {        update(l,m,rt<<1,L,m,c);        update(m+1,r,rt<<1|1,m+1,R,c);    }    pushup(rt);}int query(int l,int r,int rt,int c){    if(l==r)    {        return sum[rt];    }    pushdown(l,r,rt);    int m=(l+r)>>1;    int res=0;    if(c<=m) res=query(l,m,rt<<1,c);    else res=query(m+1,r,rt<<1|1,c);    return res;}void change(int x,int y,int c){    int f1=top[x];    int f2=top[y];    while(f1!=f2)    {        if(deep[f1]<deep[f2])        {            swap(x,y);            swap(f1,f2);        }        update(1,n,1,p[f1],p[x],c);        x=fa[f1];        f1=top[x];    }    if(deep[x]>deep[y]) swap(x,y);    update(1,n,1,p[x],p[y],c);}int main(){    int i;    while(scanf("%d%d%d",&n,&m,&q)!=EOF)    {        init();        for(i=1;i<=n;i++)        {            scanf("%d",&num[i]);        }        for(i=1;i<=m;i++)        {            int a,b;            scanf("%d%d",&a,&b);            add(a,b);            add(b,a);        }        dfs1(1,0,0);        dfs2(1,1);        build(1,n,1);        char op[5];        while(q--)        {            scanf("%s",op);            if(strcmp(op,"Q")==0)            {                int x;                scanf("%d",&x);                printf("%d\n",query(1,n,1,p[x]));            }            else if(strcmp(op,"I")==0)            {                int a,b,c;                scanf("%d%d%d",&a,&b,&c);                change(a,b,c);            }            else            {                int a,b,c;                scanf("%d%d%d",&a,&b,&c);                change(a,b,-c);            }        }    }    return 0;}