[2018.10雅礼] Equation 题解【树状数组】【dfs序】【树上差分】
点击量：225
感觉这个题最棘手的是树状数组部分……（前提是想到正解
题目描述
有一棵\(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;
}
… [Trackback]
[…] Information on that Topic: wjyyy.top/1795.html […]