题目链接：http://poj.org/problem?id=1984

题意：给定n个farm，m条边连接farm，k组询问，询问根据前t3条边求t1到t2的曼哈顿距离，若不可求则输出-1。

思路：类似与poj1182，也是并查集的向量运用。用root[i]表示farm i的祖先，x[i],y[i]分别表示i到其祖先的曼哈顿距离的横纵坐标，这里离线化先保存边的信息，在询问的时候更新边的信息，具体的合并操作时x[i],y[i]的运算手动推一下就明白了。

AC代码：

1 #include
     
       2 #include
      
        3 using namespace std; 4  5 const int maxn=40005; 6 struct node{ 7     int f1,f2,l; 8     char c; 9 }a[maxn];10 11 int n,m,k,root[maxn],x[maxn],y[maxn];12 13 int getr(int kk){14     if(root[kk]==kk) return kk;15     else{16         int tmp=root[kk];17         root[kk]=getr(root[kk]);18         x[kk]+=x[tmp];19         y[kk]+=y[tmp];20         return root[kk];21     }22 }23 24 int main(){25     scanf("%d%d",&n,&m);26     for(int i=1;i<=n;++i)27         root[i]=i,x[i]=y[i]=0;28     for(int i=1;i<=m;++i)29         scanf("%d%d%d %c",&a[i].f1,&a[i].f2,&a[i].l,&a[i].c);30     int p=0;31     scanf("%d",&k);32     while(k--){33         int t1,t2,t3;34         scanf("%d%d%d",&t1,&t2,&t3);35         for(int i=p+1;i<=t3;++i){36             int r1=getr(a[i].f1),r2=getr(a[i].f2),xx,yy;    37             if(a[i].c=='N') xx=0,yy=a[i].l;38             else if(a[i].c=='S') xx=0,yy=-a[i].l;39             else if(a[i].c=='E') xx=a[i].l,yy=0;40             else xx=-a[i].l,yy=0;41             root[r2]=r1;42             x[r2]=x[a[i].f1]-xx-x[a[i].f2];43             y[r2]=y[a[i].f1]-yy-y[a[i].f2];44         }45         p=t3;46         int r1=getr(t1),r2=getr(t2);47         if(r1==r2)48             printf("%d\n",abs(x[t1]-x[t2])+abs(y[t1]-y[t2]));49         else50             printf("-1\n");51     }52     return 0;53 }