【树状数组】【dfs序】【树上差分】[2018.10雅礼] Equation 题解

 

    感觉这个题最棘手的是树状数组部分……(前提是想到正解

 

题目描述

有一棵\(n\)个点的以\(1\)为根的树,以及\(n\)个整数变量\(x_i\)。树上\(i\)的父亲是\(f_i\),每条边\((i,f_i)\)有一个权值\(w_i\),表示一个方程\(x_i+x_{f_i}=w_i\),这\(n-1\)个方程构成了一个方程组。

 

现在给出\(q\)个操作,有两种类型:

 

  • \(1\ u\ v\ s\),表示询问加上\(x_u+x_v=s\)这个方程后,整个方程组的解的情况。具体来说,如果方程有唯一解,输出此时\(x_1\)的值;如果有无限多个解,输出inf;如果无解,输出none. 注意每个询问是独立的.
  • \(2\ u\ w\),表示将\(w_u\)修改为\(w\).

输入输出格式

输入格式:

从文件equation.in中读入数据.

 

第一行两个整数\(n,q\)。

 

接下来\(n-1\)行,第\(i\)行有两个整数\(f_{i+1}\)和\(w_{i+1}\)。

 

接下来\(q\)行,每行表示一个操作,格式见问题描述。

 

输出格式:

 

输出到文件equation.out中.

 

对于每个询问输出一行表示答案.

输入输出样例

输入样例#1:

2 7
1 4
1 1 2 5
1 1 2 4
1 1 1 3
1 2 2 6
2 2 3
1 2 2 10
1 2 2 -10
输出样例#1:

none
inf
none
1
-2
8

说明

对于所有数据,有\(1\le n,q\le 10^6,1\le f_i\le i -1,1\le u,v\le n; -10^3\le w,w_i\le 10^3,-10^9\le s\le 10^9\).

  • \(\text{Subtask1}(3\%),n\le 10,q=0\).
  • \(\text{Subtask2}(18\%), n=2\).
  • \(\text{Subtask3}(32\%), n,q\le 10^3\).
  • \(\text{Subtask4}(33\%), n,q\le 10^5\).
  • \(\text{Subtask5}(14\%)\),没有特殊的约束.

 

题解:

    首先看到这个题的第一眼是高斯消元。但是复杂度很高,并且对于自由元和无解的处理难以掌握。那么我们直接在图上找关于方程组的信息。

 

    因为每次询问单独添加一条边,一定会形成环。那么这个环连着的那条链上的信息就要被求出来。

 

    我们任取一条\(1\)到\(m\)的链,可得

$$\left\{\begin{matrix}
x_1+x_2=w_1\\
x_2+x_3=w_2\\
\dots\\
x_{m-1}+x_m=w_{m-1}
\end{matrix}\right.$$

    当\(m\)为奇数时,区间数为偶数,可带入消元得\(x_1-x_m=w_1-w_2+\dots+w_{m-2}-w_{m-1}\);当\(m\)为偶数时,区间数为奇数,同理可得\(x_1+x_m=w_1-w_2+\dots-w_{m-2}+w_{m-1}\)。注意前后式子的加减不同,导致式子右边最后一个符号不同。

 

    我们在树上任取两点,只要不满足互为祖孙关系,那么就要由两段链拼接起来。因此考虑在树上做前缀和。

 

    根据上面的式子推知每个点的信息:每个点一定可以被表示为\(x_m=k_m-x_1\)或者\(x_m=k_m+x_1\)。这个加减也是根据深度的奇偶来定的。那么对于两个点\(i,j\),有\(x_i=k_i+t_i\times x_1,x_j=k_j+t_i\times x_1,t_i,t_j\in\{0,1\}\)。此时只有两个变量,消元也是非常方便的,就可以根据判断\(t\)情况来确定是否有解即可。

 

    重点是这个题要中途修改。不过好在只改一个点,那么考虑此时更改的那条边对哪些节点做出了贡献,贡献为正还是为负。可以发现,更改的那条边的儿子节点的子树都受到了影响。为了避免讨论正负,我们把边按深度分成奇偶,方便起见,一条边的深度与这条边的儿子保持一致。

 

    对于深度为奇数的点,对它而言做正贡献的是深度为奇的边,做负贡献的是深度为偶的边。上文提到,受影响的是子树,那么我们把以这个边的儿子节点为根的子树全部加上这条边的贡献,用树状数组维护。如果这条边的深度是奇数,那么在“奇”树状数组中,把它的子树全部加上这条边的影响。偶数同理。

 

    修改完后,我们对于奇数点,可以直接在奇树状数组中查询它祖先对它的正影响,以及在偶树状数组中查询负影响,两者按符号相加就是这个点当前的\(k_i\)。

 

    求完\(k_i\)后,我们还需要通过两个点的深度差奇偶性来判断他们消元的方式(加还是减)。如果得到\(x_i=x_1+k_i,x_j=x_1+k_j(t_i\cdot t_j>0,t)\)是\(x_1\)的系数\()\),就判断\(x_i+x_j=w\)是否成立,代进去得\(2x_1+k_i+k_j=w\)。直接移项,判断解是否为整数即可,不是则为none。如果得到\(x_i=-x_1+k_i,x_j=x_1+k_j(t_i\cdot t_j<0)\),那么两式相加,判断是恒成立或者无解即可。

 

    思维量比较大且代码技巧比较丰富的一道题。

 

Code:

#include<cstdio>
#include<cstring>
#define ll long long
struct edge
{
    int n,nxt;
    ll v;
    edge(int n,int nxt,ll v)
    {
        this->n=n;
        this->nxt=nxt;
        this->v=v;
    }
    edge(){}
}e[2000000];
int head[1000010],ecnt=-1;
void add(int from,int to,ll v)
{
    e[++ecnt]=edge(to,head[from],v);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to],v);
    head[to]=ecnt;
}
int n;
ll c[2][1000010];//分别存奇树状数组和偶树状数组
int lowbit(int x)
{
    return x&(-x);
}
ll ask(int p,int x)
{
    ll ans=0;
    while(x)
    {
        ans+=c[p][x];
        x-=lowbit(x);
    }
    return ans;
}
void change(int p,int x,ll t)
{
    while(x<=n)
    {
        c[p][x]+=t;
        x+=lowbit(x);
    }
}

ll x[1000010];
int dfn[1000010],sz[1000010],cnt=0;
int d[1000010];
void dfs(int t,int from)//求dfs序和子树大小
{
    sz[t]=1;
    dfn[t]=++cnt;
    for(int i=head[t];~i;i=e[i].nxt)
        if(e[i].n!=from)
        {
            d[e[i].n]=d[t]+1;
            dfs(e[i].n,t);
            sz[t]+=sz[e[i].n];
        }
}
long long fa[1000010];
int main()
{
    memset(head,-1,sizeof(head));
    int q,u,v,op;
    ll w;
    scanf("%d%d",&n,&q);
    for(int i=2;i<=n;++i)
    {
        scanf("%d%lld",&u,&w);
        add(i,u,w);
        fa[i]=w;
    }
    d[1]=1;
    dfs(1,1);
    for(int i=1;i<=n;++i)
    {
        change(d[i]&1,dfn[i],fa[i]);//整个子树中相同奇偶性的点都会受到这么多的影响
        change(d[i]&1,dfn[i]+sz[i],-fa[i]);
    }

    for(int i=1;i<=q;++i)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%lld",&u,&v,&w);
            x[u]=ask(d[u]&1,dfn[u])-ask(d[u]&1^1,dfn[u]);//求正负贡献之和
            x[v]=ask(d[v]&1,dfn[v])-ask(d[v]&1^1,dfn[v]);
            if((d[u]+d[v])&1)//对照题解中写的情况,这里应该是t_i*t_j<0
            {
                if(x[u]+x[v]==w)
                    puts("inf");
                else
                    puts("none");
            }

            else//注意谁正谁负
            {
                if(d[u]&1)//t+2x
                {
                    if((w-x[u]-x[v])&1)
                        puts("none");
                    else
                        printf("%lld\n",(w-x[u]-x[v])/2);
                }
                else//t-2x
                {
                    if((x[u]+x[v]-w)&1)
                        puts("none");
                    else
                        printf("%lld\n",(x[u]+x[v]-w)/2);
                }
            }
        }
        else
        {
            scanf("%d%lld",&u,&w);
            ll D=w-fa[u];//修改的是增量而不是权值
            change(d[u]&1,dfn[u],D);
            D=-w+fa[u];
            change(d[u]&1,dfn[u]+sz[u],D);
            fa[u]=w;
        }
    }
    return 0;
}