【poj3237】Tree

此题是维护一个边权，但是对边线段树不好写，所以可以把边权化归为点权，但是边比点少1，怎么表示呢，一个常用的办法是，我们考虑将一棵无根树转化为有根树之后，对于除了根以外每个点有且只有一条父边，而且可以确定的，所以我们可以将边权化归到点权上，然后就是树链剖分裸题了，我是跟hzwer学长一样，加了个倍增求LCA，具体见代码

#include
#include
#include
#include
#include

using namespace std;
struct edge{
    int v,w,next;
}e[20010];
struct seg{
    int l,r,mx,mn,tag;
}tr[80010];
const int N=10010,inf=0x3f3f3f3f;
int head[N],to[N],tp[N],qx,tree[N];
int bin[15];
int num[N],fa[N][14],h[N],size[N];
int T,n,ql,m,te,sz;
inline int F()
{
    register int aa,bb;register char ch;
    while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');ch=='-'?aa=bb=0:(aa=ch-'0',bb=1);
    while(ch=getchar(),ch<='9'&&ch>='0')aa=(aa<<3)+(aa<<1)+ch-'0';return bb?aa:-aa;
}
void add(int u,int v,int w)
{
    e[++te].v=v;
    e[te].w=w;
    e[te].next=head[u];
    head[u]=te;
}
void clear()
{
    sz=0,te=1;memset(head,0,sizeof(head));
    memset(fa,0,sizeof(fa));fa[1][0]=0;size[0]=0,h[1]=1;
}
void updata(int k)
{
    tr[k].mn=min(tr[k<<1].mn,tr[k<<1|1].mn);
    tr[k].mx=max(tr[k<<1].mx,tr[k<<1|1].mx);
}
void solve(int &x,int &y){int t=x;x=-y,y=-t;}
void pushdown(int k)
{
    int l=tr[k].l,r=tr[k].r;
    if (l==r||!tr[k].tag)return;tr[k].tag=0;
    tr[k<<1].tag^=1;tr[k<<1|1].tag^=1;
    solve(tr[k<<1].mn,tr[k<<1].mx);
    solve(tr[k<<1|1].mn,tr[k<<1|1].mx);
}
void build(int k,int l,int r)
{
    tr[k].l=l,tr[k].r=r;
    tr[k].tag=0;tr[k].mn=inf,tr[k].mx=-inf;
    if (l==r)return;
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
}
void change(int k,int x,int val)
{
    pushdown(k);
    int l=tr[k].l,r=tr[k].r;
    if (l==r)
    {
        tr[k].mn=tr[k].mx=val;return;
    }
    int mid=(l+r)>>1;
    if (x<=mid)change(k<<1,x,val);
    else change(k<<1|1,x,val);
    updata(k);
}
void query(int k,int x,int y)
{
    pushdown(k);
    int l=tr[k].l,r=tr[k].r;
    if (x<=l&&y>=r)
    {
        ql=max(ql,tr[k].mx);
        return ;
    }
    int mid=(l+r)>>1;
    if (x<=mid)query(k<<1,x,y);
    if (y>mid)query(k<<1|1,x,y);
}
void rever(int k,int x,int y)
{
    pushdown(k);
    int l=tr[k].l,r=tr[k].r;
    if (x<=l&&y>=r)
    {
        solve(tr[k].mn,tr[k].mx);
        tr[k].tag=1;return;
    }
    int mid=(l+r)>>1;
    if (x<=mid)rever(k<<1,x,y);
    if (y>mid)rever(k<<1|1,x,y);
    updata(k);
}
void dfs1(int x)
{
    size[x]=1;
    for (int i=1;i<=13;++i)
    if (bin[i]<=h[x])
    fa[x][i]=fa[fa[x][i-1]][i-1];
    else break;
    for (int i=head[x];i;i=e[i].next)
    {
        int v=e[i].v;
        if (v==fa[x][0])continue;
        h[v]=h[x]+1;
        fa[v][0]=x;
        dfs1(v);
        size[x]+=size[v];
    }
}
void dfs2(int x,int chain)
{
    tp[x]=chain;num[x]=++sz;
    int k=0;
    for (int i=head[x];i;i=e[i].next)
    {
        int v=e[i].v;
        if (v!=fa[x][0])
        {
            if(size[v]>size[k])k=v;
        }
        else to[i>>1]=num[x],change(1,num[x],e[i].w);
    }
    if (!k)return;
    dfs2(k,chain);
    for (int i=head[x];i;i=e[i].next)
    {
        int v=e[i].v;
        if (v!=fa[x][0]&&v!=k)
        dfs2(v,v);
    }
}
int lca(int x,int y)
{
    if (h[x]=0;--i)
    if (fa[x][i]!=fa[y][i])
    x=fa[x][i],y=fa[y][i];
    if (x==y)return x;
    return fa[x][0];
}
int solvequery(int x,int f)
{
    ql=-inf;
    while (tp[x]!=tp[f])
    {
        query(1,num[tp[x]],num[x]);
        x=fa[tp[x]][0];
    }
    if (num[f]+1<=num[x])
    query(1,num[f]+1,num[x]);
    return ql;
}
void solverever(int x,int f)
{
    while(tp[x]!=tp[f])
    {
        rever(1,num[tp[x]],num[x]);
        x=fa[tp[x]][0];
    }
    if (num[f]+1<=num[x]);
    rever(1,num[f]+1,num[x]);
}
int main()
{
    bin[0]=1;
    for (int i=1;i<15;++i)bin[i]=bin[i-1]<<1;
    T=F();
    while(T--)
    {
        clear();
        n=F();
        for (int i=1;i