pG. Safe Tariff(Easy)

$Easy$ 與

$Hard$ 僅在

$n,q$ 不同

題目敘述 :

太平洋上有

$n$ 個島嶼國家，為了方便起見將其命名為

$1$ ~

$n$ 。這些島嶼國家皆使用一個共同貨幣，他們稱其為國際銀幣。各個國家之間有許多貿易往來，其中一種便是金磚航運。並且在這些國家之間有一些固定的航線往來，這些航線也是交流與物產貿易的主要手段。每一條航線都是往返固定兩個國家。若一航線是往返國家

$u$ ，則以

$(u,v)$ 或

$(v,u)$ 表示該航線，兩種表示方法相同，代表聚客

$u$ 與國家

$v$ 可以直航交易兩地。如果國家

$u$ 與國家

$v$之間沒有航線直接往返也可能透過複數航線進行貿易。若存在一系列的航線

$(u,p_1),(p_1,p_2)...(p_r,v)$ 則國家

$u$ 與國家

$v$ 之間便可以進行貿易，反之則不行。

為了保護太平洋的生態，所有國家的共識是在任兩個島嶼國家之間都能夠進行貿易往來的前提下維持
盡可能少的航線。顯而易見的，在

$n$ 個國家的情況下僅需要

$n-1$ 條航線就足夠了。

每個國家為了保護自己內部的產業不受到外部的低價商品傾銷、惡性競爭。因此對各項商品都設定有關稅。而在太平洋上關稅課徵的方式是針對貨物數量，在每一航線上船上所装載的商品都要被抽一次税金。依據商品的種類不同有不同的抽税方式；而針對金磚，則是每一個保險箱要課徵

$c$ 個國際銀幣。然而因為金磚航運生意普普，因此所有國家起初並不是非常重視，也就沒有對其課徵關稅。

黃瓜學長是一個專做金磚航運的

$"$為何年輕人都不愛讀現代詩

$"$ 企業的老闆，客戶所在的國家與當下金磚能出貨的國家不同，可能會被課徵關稅也不同。他希望可以收取合理的價格以避免無法獲利，或是被投訴價格過高不符合公平貿易。因此他需要計算航線上會被課徵多少關稅。

並且，由於最近發生金融危機，加上疫情高漲，許多原來不課徵關稅的國家也嗅到了這股商機，選擇開始課徵關稅。所以黃瓜學長必須隨時調整售價來因應關稅的變動。以免傷害到

$"$為何年輕人都不愛讀現代詩

$"$ 的競爭力。

輸入說明 :

• 第一行輸入
  $2$ 個數字
  $n$
  $q$ ，代表有
  $n$ 個國家，
  $q$ 次操作
• 接下來有
  $n-1$ 行，每行有
  $2$ 個數字
  $u$
  $v$ ，代表國家
  $(u,v)$ 之間有直接的航道。
• 接下來有
  $q$ 行，每行有
  $3$ 個數字
  $op$
  $a$
  $b$
• 若
  $op=1$ ，代表黃瓜學長收到訂單(從國家
  $a$ 輸送到國家
  $b$ )
• 否則
  $op=2$ ，代表國家
  $a$ ，將關稅改為
  $b$ 國際銀幣/保險箱

$op\in \text{{1,2}}$

$n$

$,$

$q$

$\le {10}^3$

$a$

$,$

$b$

$\le n$

輸出說明 :

對於

$op==1$ 輸出所需關稅(輸出國

$(a)$ 不會課關稅，但輸入國

$(b)$ 會)。

範例輸入1 :

7 10
6 5
7 5
4 3
4 5
4 2
6 1
1 3 7
1 3 1
2 6 207
1 7 4
1 6 4
2 2 683
2 3 119
1 5 6
2 1 579
2 1 947

範例輸出1 :

0
0
0
0
207

子題組與配分

• 第一子題組 : 無其他限制，占 100%

題解程式碼

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=100010;
const ll INF=0x3f3f3f3f3f3f3f3f;
using pii=pair<int,int>;

int n;
int dis[N];
vector<int> g[N];

int query(int u,int v,int p=-1,int sum=0){
    if(u==v) return sum+dis[v];
    int ret=0;
    for(auto e:g[u]) if(e!=p){
        ret+=query(e,v,u,sum+dis[u]);
    }
    return ret;
}

int modify(int u,int x){
    dis[u]=x;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    int q;
    cin>>n>>q;
    vector<pii> es;

    for(int i=1;i<n;++i){
        int f,t;
        cin>>f>>t;
        g[f].emplace_back(t);
        g[t].emplace_back(f);
    }

    for(int i=0;i<q;++i){
        int op;
        cin>>op;
        if(op==1){// query
            int u,v;
            cin>>u>>v;
            cout<<query(u,v)-dis[u]<<"\n";
        }else{// op==2 modfiy
            int u,x;
            cin>>u>>x;
            modify(u,x);
        }
    }
}