Description 小Q在電子工藝實習課上學習焊接電路板。一塊電路板由若幹個元件組成，我們不妨稱之為節點，並將其用數 字1,2,3….進行標號。電路板的各個節點由若幹不相交的導線相連接，且對於電路板的任何兩個節點，都存在且僅 存在一條通路（通路指連接兩個元件的導線序列）。在電路板上存在一個特殊的 ...
Submit: 3285 Solved: 1286
[Submit][Status][Discuss]
Description
小Q在電子工藝實習課上學習焊接電路板。一塊電路板由若幹個元件組成，我們不妨稱之為節點，並將其用數 字1,2,3….進行標號。電路板的各個節點由若幹不相交的導線相連接，且對於電路板的任何兩個節點，都存在且僅 存在一條通路（通路指連接兩個元件的導線序列）。在電路板上存在一個特殊的元件稱為“激發器”。當激發器工 作後，產生一個激勵電流，通過導線傳向每一個它所連接的節點。而中間節點接收到激勵電流後，得到信息，並將 該激勵電流傳向與它連接並且尚未接收到激勵電流的節點。最終，激烈電流將到達一些“終止節點”——接收激勵 電流之後不再轉發的節點。激勵電流在導線上的傳播是需要花費時間的，對於每條邊e，激勵電流通過它需要的時 間為te，而節點接收到激勵電流後的轉發可以認為是在瞬間完成的。現在這塊電路板要求每一個“終止節點”同時 得到激勵電路——即保持時態同步。由於當前的構造並不符合時態同步的要求，故需要通過改變連接線的構造。目 前小Q有一個道具，使用一次該道具，可以使得激勵電流通過某條連接導線的時間增加一個單位。請問小Q最少使用 多少次道具才可使得所有的“終止節點”時態同步？Input
第一行包含一個正整數N，表示電路板中節點的個數。第二行包含一個整數S，為該電路板的激發器的編號。接 下來N-1行，每行三個整數a , b , t。表示該條導線連接節點a與節點b，且激勵電流通過這條導線需要t個單位時 間Output
僅包含一個整數V，為小Q最少使用的道具次數
Sample Input
31
1 2 1
1 3 3
Sample Output
2HINT
N ≤ 500000，te ≤ 1000000
Source
一道比較好想但是代碼實現很巧妙的題 首先可以證明的是，終止的時間就是從根節點出發最長鏈的權值 其次，如果可以修改一條路徑使得更接近條件，那麼這樣一定會比單獨改兒子更優 因此我們考慮貪心，找出每個點出發的最長鏈，然後答案加上最長鏈與子節點的最長鏈的差值(相當於往上補)
// luogu-judger-enable-o2 #include<cstdio> #include<vector> #include<cstring> #define LL long long using namespace std; const int MAXN=1e6+10; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++) char buf[1<<22],*p1=buf,*p2=buf; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } struct Edge { int v,w; }; vector<Edge>v[MAXN]; LL mx[MAXN], Ans = 0; void Dfs(int now, int fa) { for(int i=0;i<v[now].size();i++) { if(v[now][i].v != fa) { Dfs(v[now][i].v, now); mx[now] = max(mx[now], mx[ v[now][i].v ] + v[now][i].w); } } for(int i=0;i<v[now].size();i++) { if(v[now][i].v != fa) Ans += mx[now] - mx[ v[now][i].v ] - v[now][i].w; } } int N, root; int main() { #ifdef WIN32 freopen("a.in","r",stdin); #endif N = read(), root = read(); for(int i=1;i<=N-1;i++) { int x = read(), y = read(), z = read(); v[x].push_back((Edge){y,z}); v[y].push_back((Edge){x,z}); } Dfs(root, -1); printf("%lld",Ans); return 0; }
