[欧拉序][树上线段树][LCA] POJ 2763 Housewife Wind

https://cn.vjudge.net/problem/POJ-2763

欧拉序线段树裸题，每次要求出两点之间的距离，单点修改，区间查询。

欧拉序其实就是把树拍扁的一种方法。。。对给定的树先求出欧拉序，在欧拉序上通过权值的正负来抵消多余的往返操作，然后每次求得时候先求LCA，再求出lca到两个端点的距离相加即可。有了欧拉序LCA就是一个rmq问题，用线段树做就能实现动态求lca，然后端点距离可以用BIT或者仍然用线段树做，求和最后输出即为答案。

实现的主要注意点是下标之间的关系。。。。这其中欧拉序求出来的点个数是2*n-1，然后BIT上存储的又是2n-2个间隔，然后BIT差分又得考虑左端点往前移动一下。。

//#include
#include
#include
#include
#include
#include
#include

using namespace std;

typedef long long LL;
const int maxn=1e5+5;
const int mod=1e9+7;

struct edge
{
    int id,to,cost;
    edge(int id,int to,int cost):id(id),to(to),cost(cost){}
};
vector G[maxn];
int root;
int a[maxn],b[maxn],w[maxn];
int vs[maxn<<1],depth[maxn<<1],id[maxn],es[maxn<<1];
int minv[maxn<<3],mind[maxn<<3];
int n,q,s,op,u,tw,fn;

void maintain(int o,int l,int r)
{
    minv[o]=min(minv[o<<1],minv[o<<1|1]);
    mind[o]=minv[o<<1]>1;
        if(ps<=mid)update(o<<1,l,mid);
        else update(o<<1|1,mid+1,r);
    }
    maintain(o,l,r);
}

int ql,qr;
int query(int o,int l,int r)
{
    if(ql<=l&&r<=qr)
        return mind[o];
    else
    {
        int mid=(l+r)>>1,a1=mod,a2=mod;
        if(ql<=mid)
            a1=query(o<<1,l,mid);
        if(mid>1;
        initRmq(o<<1,l,mid);
        initRmq(o<<1|1,mid+1,r);
        maintain(o,l,r);
    }

}

int btree[maxn<<2];
void add(int x,int p)
{
    while(x<=fn)
    {
        btree[x]+=p;
        x+=(x&(-x));
    }
    return ;
}

int sum(int k)
{
    int ans=0;
    while(k>0)
    {
        ans+=btree[k];
        k-=(k&(-k));
    }
    return ans;
}

int clk=1;
void dfs(int x,int f,int d)
{
    id[x]=clk;
    vs[clk]=x;
    depth[clk++]=d;
    int len=G[x].size();
    int id,to,cost;
    for (int i=0;iqr)
        swap(ql,qr);
    int tmp=query(1,1,fn);
    return vs[tmp];
}

int main()
{
//    std::ios::sync_with_stdio(false);
//    cin.tie(0);
//    cout.tie(0);

    cin>>n>>q>>s;
    fn=2*n-1;
    for (int i=1;i