样例输入

10 5 5

1 5 4

2 5 4

3 6 5

1 9 9

6 6 2

1 9

2 6

1 2

3 5

1 7

样例输出

9

6

1

3

UNKNOWN

 

 

看到这种题一开始以为是线段树后来发现不能存区间然后我就不知道其他方法了……终于被告知是并查集（从来没有做过这种题！）

引用 由于是区间合并，但是你无法确定他们之间的关系，所以应该想到并查集将他们联系起来（巧妙啊！又学到了新知识！）

fa1=fa2的时候是这样的

比如a_________________c (权值10)

                  b__________c (6)

     a______b (4)

    我把前两个连接起来后 有 dist[a]:=-10;dist[b]:=-6;fa[a]:=c;fa[b]:=c;

    加上第三个以后有 fa1:=c;fa2:=c;

                            dist[fa1]:=dist[r]-dist[l]-x 就应该是 dist[c]=dist[b]-dist[a]-4=-6+10-4=0

program p36;

var

  dist,fa:array[0..5001] of longint;

  n,m,k:longint;

function find(x:longint):longint;

var tem:longint;

begin

  if (fa[x]=x) then exit(x);

  tem:=fa[x];

  fa[x]:=find(fa[x]);

  if (fa[x]<>tem) then dist[x]:=dist[x]+dist[tem];

  exit(fa[x]);

end;

 

procedure insert(l,r,x:longint);

var fa1,fa2:longint;

begin

  fa1:=find(l);

  fa2:=find(r);

  fa[fa1]:=fa2;

  dist[fa1]:=dist[r]-dist[l]-x;

end;

procedure init;

var l,r,x,i:longint;

begin

  assign(input,'p36.in');reset(input);

  assign(output,'p36.out');rewrite(output);

  fillchar(dist,sizeof(dist),0);

  readln(n,m,k);

  for i:=1 to n do fa[i]:=i;

  for i:=1 to m do begin

    readln(l,r,x);

    insert(l-1,r,x);

  end;

end;

procedure main;

var i,l,r,fa1,fa2:longint;

begin

  for i:=1 to k do begin

    readln(l,r);

    fa1:=find(l-1);

    fa2:=find(r);

    if (fa1<>fa2) then writeln('UNKNOWN') else writeln(dist[r]-dist[l-1]);

  end;

end;

procedure terminate;

begin

  close(input);close(output);

end;

begin

  init;

  main;

  terminate;

end.