Equation

Source and Judge

雅礼noip模拟题

Problem

给一棵n个点的树,每个点代表一个未知数xi
每条边给出权值,表示两个未知数的和
q个询问,op=1表示询问:暂时补充一条边,唯一解输出x1,多解输出inf,无解输出none
op=2表示修改第x个点,向上的那条边的权值
n不超过1000000

Record

2h

Analysis

请先思考后再展开

写了有一点慢,比赛没时间写完暴力去拍,幸运地ac了

这道题主要是思维,还需要一点点运气
因为输出x1,因为n个未知数的方程组需要n个方程,所以现在一定是不能解完的
将第i个点向上的那条边,编号设定为i
然后考虑高斯消元的思想,第i个点上面的边,和下面的几条边都有公共元,
然后我们定义第i条边的主元是xi,所以向下消除
然后设1向下的边为深度1,那么深度为奇数,下端编号为t的边,参与的未知数是xt+x1,否则是xt-x1
然后边的权值,经过高斯消元后,形式为 $[奇数则取反] \sum -si$
(具体符号请读者自行推导,很好想的)

然后对于每个修改操作,相当于对子树的所有边修改,然后具体的修改按照「当前边深度奇偶性和那条边深度的奇偶性的异或值」
所以开两个树状数组,差分一下就好了

然后对于询问,把两条边连接在了一起

  1. 两条边深度奇偶性相同,那么形式为 0=S-权值1-权值2
  2. 奇偶性不同,那么形式为 2x1=S-权值1-权值2
    那么这两个方程的解的情况,自己随便判断一下就好了

时间复杂度 $O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#ifdef DEBUG
const int LOCAL=1;
#else
const int LOCAL=0;
#endif

namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;

const int MAX_N=1100000;
int n;
struct Bit
{
ll bit[MAX_N];
int lowbit(int x) {return x&-x;}
void change(int x,ll c) {while(x<=n) bit[x]+=c,x+=lowbit(x);}
ll getsum(int x) {ll ans=0;while(x>=1) ans+=bit[x],x-=lowbit(x);return ans;}
}bt[2];

int hou[MAX_N],siz[MAX_N],dfn[MAX_N],dep[MAX_N];
int fa[MAX_N];int up[MAX_N];
struct Edge{int y,g,c;}e[MAX_N];
int ln=0;void ins(int x,int y,int c) {e[++ln]=(Edge){y,hou[x],c};hou[x]=ln;}
int id=0;
void dfs(int x)
{
siz[x]=1;dfn[x]=++id;
bt[dep[x]&1].change(dfn[x],up[x]);
bt[!(dep[x]&1)].change(dfn[x],-up[x]);

for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;
dep[y]=dep[x]+1;
dfs(y);siz[x]+=siz[y];
}

bt[dep[x]&1].change(dfn[x]+siz[x],-up[x]);
bt[!(dep[x]&1)].change(dfn[x]+siz[x],up[x]);
}

void main()
{
if(!LOCAL) freopen("equation.in","r",stdin);
if(!LOCAL) freopen("equation.out","w",stdout);

int q;scanf("%d%d",&n,&q);
for(int i=2;i<=n;i++) scanf("%d%d",&fa[i],&up[i]),ins(fa[i],i,up[i]);
dep[1]=0;dfs(1);
while(q--)
{
int op,x,y;scanf("%d%d%d",&op,&x,&y);
if(op==1)
{
int s;scanf("%d",&s);
if(dep[x]>dep[y]) swap(x,y);

ll geta=bt[dep[x]&1].getsum(dfn[x]);
ll getb=bt[dep[y]&1].getsum(dfn[y]);
ll now=(ll)s-geta-getb;

if( (dep[x]&1) != (dep[y]&1) )
{
if(now==0) puts("inf");
else puts("none");
}
else
{
if(now&1) puts("none");
else
{
if(dep[x]&1) printf("%lld\n",-now/2);
else printf("%lld\n",now/2);
}
}
}
else
{
ll old=up[x],now=y;
bt[dep[x]&1].change(dfn[x],(now-old));
bt[dep[x]&1].change(dfn[x]+siz[x],-(now-old));
bt[!(dep[x]&1)].change(dfn[x],-(now-old));
bt[!(dep[x]&1)].change(dfn[x]+siz[x],(now-old));
up[x]=now;
}
}
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/5574.html
转载请注明出处,谢谢!