这个题名字也真是……

思路和我以前提到过的NOI2015 D1T2的做法是相似的，不过这题貌似int会爆精度……我这SB开始没发现，后来改了还慢慢出错……然后慢慢改……终于AC了……

我本来以为这个YY思路只有我和诸位读者知道，结果发现是貌似是ydc发明的……比我早的高明的不知哪里去了……

代码：

/**************************************************************
    Problem: 4034
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2944 ms
    Memory:16220 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define REP(i,n) for(i=0;i<(n);i++)
#define REPB(i,n) for(i=1;i<=(n);i++)
#define SEG_CS int o,int L,int R
#define DEF_MID int M=L+(R-L)/2
#define DEF_CLDS int lc=o*2,rc=o*2+1
const int maxn=100001;
// Segment Tree
long long sumv[maxn*4],addv[maxn*4];
void maintain(SEG_CS){
    DEF_CLDS;
    sumv[o]=0;
    if(R>L)
        sumv[o]=sumv[lc]+sumv[rc];
    if(addv[o])
        sumv[o]+=addv[o]*(R-L+1);
}
int ql,qr;
long long v;
void update(SEG_CS){
    DEF_CLDS;
    if(ql<=L && R<=qr){
        addv[o]+=v;
    }else{
        DEF_MID;
        if(ql<=M)
            update(lc,L,M);
        if(qr>M)
            update(rc,M+1,R);
    }
    maintain(o,L,R);
}
long long _sum;
void query(SEG_CS,long long add){
    if(ql<=L && R<=qr){
        _sum+=sumv[o]+add*(R-L+1);
    }else{
        DEF_MID;
        if(ql<=M)
            query(o*2,L,M,add+addv[o]);
        if(qr>M)
            query(o*2+1,M+1,R,add+addv[o]);
    }
}
int n;
inline void change(int l,int r,long value){
    ql=l;
    qr=r;
    v=value;
    update(1,1,n);
}
inline long long get_sum(int l,int r){
    ql=l;
    qr=r;
    _sum=0;
    query(1,1,n,0);
    return _sum;
}
// Graph
vector<int> G[maxn];
inline void Add_Edge(int x,int y){
    G[x].push_back(y);
    G[y].push_back(x);
}
// Heavy Desc
bool vis[maxn];
int dep[maxn],siz[maxn],son[maxn],fa[maxn];
void dfs_1(int x,int father,int depth){
    vis[x]=true;
    fa[x]=father;
    dep[x]=depth;
    siz[x]=1;
    int i,temp,max_siz=0;
    REP(i,G[x].size()){
        temp=G[x][i];
        if(!vis[temp]){
            dfs_1(temp,x,depth+1);
            siz[x]+=siz[temp];
            if(siz[temp]>max_siz){
                son[x]=temp;
                max_siz=siz[temp];
            }
        }
    }
}
int tot=0;
int tid[maxn],top[maxn];
long long d[maxn];
void dfs_2(int x,int a){
    vis[x]=true;
    tid[x]=++tot;
    top[x]=a;
    change(tot,tot,d[x]);
    if(son[x])
        dfs_2(son[x],a);
    else
        return;
    int i,temp;
    REP(i,G[x].size()){
        temp=G[x][i];
        if(!vis[temp])
            dfs_2(temp,temp);
    }
}
inline void change_tree(int x,long long value){
    change(tid[x],tid[x]+siz[x]-1,value);
}
inline void change_v(int x,long long value){
    change(tid[x],tid[x],value);
}
inline long long the_query(int x){
    long long ans=0;
    do{
        ans+=get_sum(tid[top[x]],tid[x]);
        x=fa[top[x]];
    }while(x);
    return ans;
}
int main(){
    int m,u,v;
    long long c;
    register int i;
    scanf("%d%d",&n,&m);
    REPB(i,n)
        scanf("%lld",&d[i]);
    REP(i,n-1){
        scanf("%d%d",&u,&v);
        Add_Edge(u,v);
    }
    dfs_1(1,0,1);
    memset(vis,0,sizeof(vis));
    dfs_2(1,1);
    REP(i,m){
        scanf("%d%d",&u,&v);
        if(u==3){
            printf("%lld\n",the_query(v));
        }else{
            scanf("%lld",&c);
            if(u==1){
                change_v(v,c);
            }else{
                change_tree(v,c);
            }
        }
    }
    return 0;
}

• 相关文章
• 全局相关文章