HDUOJ 6162 Ch’s gift

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6162

题意:给你一棵树,每个节点有固定的权值,若干询问u,v,a,b表示求uv路径上权值在[a,b]区间内的所有权值和。

思路:比赛的时候仿佛失了智,区间作差居然没想到.......我们对于路上询问的问题很容易想到树链剖分,然后用线段树或树状数组维护权值的信息,然后因为这里没有修改,所以我们直接离线做。对所有点权从小到大排序,然后我们先让这颗树上所有点的权值都为0,对于询问先以左端点为关键字进行排序,对于小于左端点的值,我们将树上对应的点权赋为他的权值的负数,然后更新答案找uv上的权值和,接着以右端点为关键字进行排序,对于小于等于右端点的值,我们讲树上的对应的点权赋为他的权值,然后把uv上的权值和加上去就是最后的答案了,相当于区间求差.........

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define MOD 1000000007
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
struct edge{
    int val;
    int id;
}e[maxn];
struct Node{
    int u,v,l,r,id;
}q[maxn];
int n,m,s,t,a,b,val[maxn];
int dfs_clock,fa[maxn],dep[maxn],siz[maxn],son[maxn],bel[maxn],id[maxn],rk[maxn];
ll ans[maxn];
bool vis[maxn];
vector<int>G[maxn];
inline bool cmpl(const Node &a,const Node &b){
    return a.l<b.l;
}
inline bool cmpr(const Node &a,const Node &b){
    return a.r<b.r;
}
inline bool cmp2(const edge&a,const edge &b){
    return a.val<b.val;
}
void dfs1(int u,int f){
    dep[u]=(f==-1?1:dep[f]+1);
    fa[u]=f;
    son[u]=-1;
    siz[u]=1;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v!=f){
            dfs1(v,u);
            siz[u]+=siz[v];
            if (son[u]==-1 || siz[v]>siz[son[u]]){
                son[u]=v;
            }
        }
    }
}
void dfs2(int u,int f){
    bel[u]=f;
    id[u]=++dfs_clock;
    rk[id[u]]=u;
    if (son[u]==-1) return;
    dfs2(son[u],f);
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v!=fa[u] && v!=son[u]){
            dfs2(v,v);
        }
    }
}
ll sum[maxn];
inline int lowbit(int x){return x&(-x);}
ll add(int x,int val){
    while (x<=n){
        sum[x]+=1LL*val;
        x+=lowbit(x);
    }
}
ll getSum(int x){
    ll res=0;
    while (x>0){
        res+=sum[x];
        x-=lowbit(x);
    }
    return res;
}
ll modify(int u,int v){
    ll ret=0;
    while (bel[u]!=bel[v]){
        if (dep[bel[u]]<dep[bel[v]]) swap(u,v);
        ret+=getSum(id[u])-getSum(id[bel[u]]-1);
        u=fa[bel[u]];
    }
    if (id[u]>id[v]) swap(u,v);
    ret+=getSum(id[v])-getSum(id[u]-1);
    return ret;
}
int main(){
    while (~scanf("%d%d",&n,&m)){
        for (int i=1;i<=n;i++) read(e[i].val),e[i].id=i,G[i].clear();
        sort(e+1,e+1+n,cmp2);
        for (int i=1;i<=n-1;i++){
            int u,v;read(u),read(v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs1(1,-1);
        dfs_clock=0;
        dfs2(1,1);
        for (int i=1;i<=m;i++){
            read(q[i].u),read(q[i].v),read(q[i].l),read(q[i].r);
            q[i].id=i;
        }
        sort(q+1,q+1+m,cmpl);
        memset(sum,0,sizeof(sum));
        int cnt=1;
        for (int i=1;i<=m;i++){
            int L=q[i].l;
            while (e[cnt].val<L && cnt<=n){
                add(id[e[cnt].id],-e[cnt].val);
                cnt++;
            }
            ans[q[i].id]=modify(q[i].u,q[i].v);
        }
        sort(q+1,q+1+m,cmpr);
        memset(sum,0,sizeof(sum));
        cnt=1;
        for (int i=1;i<=m;i++){
            int R=q[i].r;
            while (e[cnt].val<=R && cnt<=n){
                add(id[e[cnt].id],e[cnt].val);
                cnt++;
            }
            ans[q[i].id]+=modify(q[i].u,q[i].v);
        }
        for (int i=1;i<m;i++) printf("%I64d ",ans[i]);
        printf("%I64d\n",ans[m]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注